LeetCode – Evaluate Reverse Polish Notation

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

Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. For example:

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

This problem can be solved by using a stack. We can loop through each element in the given array. When it is a number, push it to the stack. When it is an operator, pop two numbers from the stack, do the calculation, and push back the result.

https://wxx5433.gitbooks.io/interview-preparation/content/part_ii_leetcode_lintcode/stack/evaluate_reverse_polish_notation.html

Use a stack.

• If the current string is an integer, we push it into the stack.
• If the current string is an operator, we pop out two numbers from the top of the stack, and do the operation on these two numbers. And then push the result back into the stack.

  public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    for (String token: tokens) {
      if (isOperator(token)) {
        stack.push(compute(token, stack.pop(), stack.pop()));
      } else {
        stack.push(Integer.valueOf(token));
      }
    }
    return stack.pop();
  }

  private boolean isOperator(String token) {
    if (token.equals("+") || token.equals("-") 
        || token.equals("*") || token.equals("/")) {
      return true;
    }
    return false;
  }

  private int compute(String operator, int num2, int num1) {
    int result = 0;
    switch (operator.charAt(0)) {
      case '+': result = num1 + num2; break;
      case '-': result = num1 - num2; break;
      case '*': result = num1 * num2; break;
      case '/': result = num1 / num2; break;
    }
    return result;
  }

 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)) { //push to stack if it is a number
    stack.push(t);
   } else {//pop numbers from stack if it is an operator
    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;
 }

    public 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;
 
    }