Evaluate the value of an arithmetic expression in Reverse Polish Notation.

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

analysis

逆波兰表达式最小的一个单元是例如3 2 +, 这就是所谓的 3+2. 但是不是所有情况都这样简单, 比如以下 5 5 / 2 +, 画成树如下图:

1
2
3
4
5
     '+'
/
'/' 2
/
5 5

有没有觉得像是 pre-order recursion 可以解决的?

pre-order recursion 可以解决, 但是用了 call stack, 本质上是一个 stack, 那么, 这道题也可以用两个 stack 来解决.

time O(n)
space 不好说

soluton2 050118

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class  {

public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList<>();

for (int i = 0; i<tokens.length; i++) {
if (tokens[i].equals("+")) {
stack.push(stack.pop()+stack.pop());
} else if (tokens[i].equals("-")) {
stack.push(-stack.pop()+stack.pop());
} else if (tokens[i].equals("*")) {
stack.push(stack.pop()*stack.pop());
} else if (tokens[i].equals("/")) {
int second = stack.pop();
int first = stack.pop();
stack.push(first/second);
} else {
stack.push(Integer.parseInt(tokens[i]));
}
}
return stack.pop();
}
}

solution1 050118

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
class  {
public int evalRPN(String[] tokens) {
Deque<String> stack = new LinkedList<>();
for(String token: tokens) {
stack.push(token);
}
return eval(stack);
}

private int eval(Deque<String> stack) {
if(!isOperator(stack.peek())) {
return Integer.parseInt(stack.pop());
}

String operator = stack.pop();
int firstOperand = eval(stack);
int secondOperand = eval(stack);

if(operator.equals("+")) {
return firstOperand+secondOperand;
}else if(operator.equals("-")) {
return secondOperand-firstOperand;
}else if(operator.equals("*")) {
return firstOperand*secondOperand;
}else{
return secondOperand/firstOperand;
}
}

private boolean isOperator(String token) {
return token.equals("+") ||
token.equals("-") ||
token.equals("*") ||
token.equals("/");
}
}