150.Evaluate Reverse Polish Notation

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?