Question:

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

  • Division between two integers should truncate toward zero.
  • The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.
Example 1:

Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Thinking:

  • Method1:
    • 使用栈，如果遇到运算符则出栈两个数组再将结果入栈。
class Solution {
    public int evalRPN(String[] tokens) {
        if(tokens == null || tokens.length == 0) return 0;
        if(tokens.length == 1) return Integer.parseInt(tokens[0]);
        Stack<Integer> stack = new Stack<>();
        int result = 0;
        for(int i = 0; i < tokens.length; i++){
            if(!isOper(tokens[i]))
                stack.push(Integer.parseInt(tokens[i]));
            else{
                Integer b = stack.pop();
                Integer a = stack.pop();
                result = operation(a, b, tokens[i]);
                stack.push(result);
            }
        }
        return result;
    }
    public static boolean isOper(String s){
        return s.equals("+") || s.equals("-") || s.equals("/") || s.equals("*");
    }
    private static int operation(Integer a, Integer b, String op){
        if(op.equals("+")) return a + b;
        else if(op.equals("-")) return a - b;
        else if(op.equals("*")) return a * b;
        else return a / b;
    }
}

二刷

  1. 这道题已经是第三次写了，很明确就是使用栈。
  2. 对于一刷的时候有了优化，使用switch取代了冗余的if-else。
  3. 这次刷犯的错：加法和乘法是有交换律的，而减法和除法不遵从交换律，所以要注意pop出来的顺序。 
    class Solution {
 public int evalRPN(String[] tokens) {
     if(tokens == null || tokens.length == 0) return 0;
     Stack<Integer> stack = new Stack<>();
     int opt1 = 0;
     int opt2 = 0;
     for(String token : tokens){
         switch(token){
             case "+":
                 stack.push(stack.pop() + stack.pop());
                 break;
             case "-":
                 opt1 = stack.pop();
                 opt2 = stack.pop();
                 stack.push(opt2 - opt1);
                 break;
             case "*":
                 stack.push(stack.pop() * stack.pop());
                 break;
             case "/":
                 opt1 = stack.pop();
                 opt2 = stack.pop();
                 stack.push(opt2 / opt1);
                 break;
             default:
                 stack.push(Integer.parseInt(token));
                 break;
         }
     }
     return stack.peek();
 }
}