150.Evaluate Reverse Polish Notation

Posted on | In

Solution 1: accepted: 12ms 86%

As long as we realize this question is best resolved using stacks, we should be fine. So we need to be clear about when to use stack: When we scan from left to right and always need to look back. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String cur = tokens[i];  // without it its 14ms
             if (cur.equals("+")) {
                 stack.push(stack.pop() + stack.pop());
             } else if (cur.equals("-")) {
                 stack.push(-stack.pop() + stack.pop());
             } else if (cur.equals("*")) {
                 stack.push(stack.pop() * stack.pop());
             } else if (cur.equals("/")) {
                 int n2 = stack.pop();
                 int n1 = stack.pop();
                 stack.push(n1 / n2);
             } else {
                 stack.push(Integer.parseInt(cur));
             }   
        }
        return stack.pop();
    }
}

How to convert standard arithmetic expressions to Reverse Polish Notation(RPN), aka postfix notation?