Java Aritmetik İşlemler Yapmak RPN ile

Posted by dogukanhan on August 27, 2017 · 3 mins read

Yapılan girişteki bilgilere dayanarak Reverse Polish Notation’a göre aritmetik işleme karar verip gerçekleştirme.Geçerli olacak işlemler  +, -, *, /.

Reverse Polish Notation Nedir?

“Reverse Polish Notation” , “Postfix Notation” ya da kısaca RPN olarak bilinen hesaplama yöntemi, parantezlere hiç gerek kalmadan işlem yapabilmemize olanak sağlar.
Bu notasyonda işlem, iki sayının ortası yerine söz konusu sayılardan sonra yazılır. (bkz: postfix)
2 + 2 yerine 2 2 + veya 2*3 yerine 2 3 * gibi..
Birden fazla işlem söz konusuysa, “stack” yani yığın sistemi kullanılır. Her yazılan sayı ve çıkan sonuç yığının en üstüne eklenir.

Örneğin;
2 3 * 1 2 + /
Bu noktada 2*3 işlemi yapılır, yığına 6 eklenir ve işleme devam edilir.
6 1 2 + /
1+ 2 işlemi de yapılarak sonuç yığına eklendiğinde işlem 6 3 / halini alır.
6/3 işlemi de yapıldığında sonuç 2 olarak bulunur.

Özetlersek, örneğimizde yer alan ve klasik gösterimi (2*3) / (1+2) olan işlemi soldan sağa doğru ilerleyerek parantezle uğraşmaksızın yapabildiğimiz bu notasyona RPN diyoruz.

Bizim yazacağımız algoritmaya göre verilen girişlerde ki sonuçlar böyle olacaktır.

[“2”, “1”, “+”, “3”, “*”] -> ((2 + 1) * 3) -> 9
[“4”, “13”, “5”, “/”, “+”] -> (4 + (13 / 5)) -> 6

1-) Düz yaklaşım

Bu problem Stack kullanarak çözülebilir.Verilen diziyi döngüye konulur ve her eleman için bir değerlendirme yapılır eğer sayı ise Stack’e puslanır.Eğer bir Aritmetik işlem operatörüyse  2 sayı Stack’ten pop edilir ve işlem gerçekleştirilir ortaya çıkan sonuç ise tekrar Stack’e pushlanır. (Not Java 7 Öncesinde Stringler Switch içerisinde kullanılmadığından derlenmeyecektir.)

public static void main(String[] args) throws IOException {
		String[] tokens = new String[] { "2", "1", "+", "4", "*" };
		System.out.println(evalRPN(tokens));
	}
 
	public static int evalRPN(String[] tokens) {
		int returnValue = 0;
		String operatorler = "+-*/";
 
                
		Stack<String> stack = new Stack<String>();
		for (String t : tokens) {
			if (!operatorler.contains(t)) { 
				stack.push(t);
			} else {
				int a = Integer.valueOf(stack.pop());
				int b = Integer.valueOf(stack.pop());
				switch (t) {
				case "+":
					stack.push(String.valueOf(a + b));
					break;
				case "-":
					stack.push(String.valueOf(b - a));
					break;
				case "*":
					stack.push(String.valueOf(a * b));
					break;
				case "/":
					stack.push(String.valueOf(b / a));
					break;
				}
			}
		}
		returnValue = Integer.valueOf(stack.pop());
		return returnValue;
	}

2-) Daha iyi bir çözüm

public static int  evalRPN(String[] tokens) {
        int returnValue = 0;
 
        String operators = "+-*/";
 
        Stack<String> stack = new Stack<String>();
 
        for(String t : tokens){
            if(!operators.contains(t)){
                stack.push(t);
            }else{
                int a = Integer.valueOf(stack.pop());
                int b = Integer.valueOf(stack.pop());
                int index = operators.indexOf(t);
                switch(index){
                    case 0:
                        stack.push(String.valueOf(a+b));
                        break;
                    case 1:
                        stack.push(String.valueOf(b-a));
                        break;
                    case 2:
                        stack.push(String.valueOf(a*b));
                        break;
                    case 3:
                        stack.push(String.valueOf(b/a));
                        break;
                }
            }
            
        }
        returnValue = Integer.valueOf(stack.pop());
        return returnValue;
    }

Kaynak :https://www.inploid.com/t/reverse-polish-notation-rpn-nedir/70036/

Kaynak :https://www.programcreek.com/2012/12/leetcode-evaluate-reverse-polish-notation/