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