NO.150 逆波兰表达式求值 中等
逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后） —— 百度百科
思路一：栈 遍历 tokens 遇到数字就入栈，遇到运算符就出栈两个数字进行运算，运算结果入栈，遍历结束栈内剩余一个元素就是最后的运算结果。
注意减法和除法不满足交换律，需要注意运算位置。例如 tokens[1,2,-] 入栈[1,2]，遇到 “-“ 应该是 -2+1；再例如 tokens[1,2,/] 入栈[1,2]，遇到 “/“ 应该是 1/2 而不是按照出栈顺序的 2/1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public int evalRPN(String[] tokens) {
if (tokens.length == 0) return 0;
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
if (token.equals("+")) {
stack.push(stack.pop() + stack.pop());
} else if (token.equals("*")) {
stack.push(stack.pop() * stack.pop());
} else if (token.equals("-")) {
stack.push(-stack.pop() + stack.pop());
} else if (token.equals("/")) {
Integer divisor = stack.pop();
stack.push(stack.pop() / divisor);
} else {
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
|
时间复杂度：O(n) 空间复杂度：O(n) 栈内元素最多 n/2+1 个
本人菜鸟，有错误请告知，感激不尽！
更多题解和源码:github