150 Evaluate Reverse Polish Notation

1. Question

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are+,-,*,/. Each operand may be an integer or another expression.
Some examples:
1
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
2
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
Copied!

2. Implementation

思路: 当遇到运算符时,要处理前面的数字,所以用stack
1
public class Solution {
2
public int evalRPN(String[] tokens) {
3
int num1 = 0, num2 = 0;
4
Stack<Integer> stack = new Stack<>();
5
6
for (String token : tokens) {
7
switch(token) {
8
case "+":
9
num1 = stack.pop();
10
num2 = stack.pop();
11
stack.push(num1 + num2);
12
break;
13
case "-":
14
num1 = stack.pop();
15
num2 = stack.pop();
16
stack.push(num2 - num1);
17
break;
18
case "*":
19
num1 = stack.pop();
20
num2 = stack.pop();
21
stack.push(num1 * num2);
22
break;
23
case "/":
24
num1 = stack.pop();
25
num2 = stack.pop();
26
stack.push(num2 / num1);
27
break;
28
default:
29
stack.push(Integer.parseInt(token));
30
31
}
32
}
33
return stack.peek();
34
}
35
}
Copied!

3. Time & Space Complexity

时间和空间都是O(n)