150. Evaluate Reverse Polish Notation

Difficulty: Medium

Evaluate the value of an arithmetic expression in .

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:

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

Example 2:

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

Example 3:

1
2
3
4
5
6
7
8
9
10
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

Solution

Language: Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class  {
public int evalRPN(String[] tokens) {
if (tokens == null || tokens.length == 0) {
return 0;
}
Deque<Object> s = new ArrayDeque<>();
for (int i = tokens.length - 1; i >= 0; i--) {
pushStack(s, tokens[i]);
}
return (Integer)s.pop();
}

private void pushStack(Deque<Object> s, String token) {
if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
s.push(token);
return;
}
Integer val = Integer.parseInt(token);
if (s.peek() instanceof String) {
s.push(val);
return;
}
while(!s.isEmpty() && s.peek() instanceof Integer) {
Integer n = (Integer) s.pop();
String operator = (String) s.pop();
int res = 0;
switch (operator) {
case "+":
res = val + n;
break;
case "-":
res = val - n;
break;
case "*":
res = val * n;
break;
case "/":
res = val / n;
break;
}
val = res;
}
s.push(val);
}

}