LeetCode 150. 逆波兰表达式求值
目录
题目描述
题意分析
输入是一个字符串数组，每个元素要么是一个整数，要么是
+、-、*、/四个运算符之一，整体构成一个后缀（逆波兰）表达式，要求算出它的值。后缀表达式的特征是运算符写在两个操作数之后，例如中缀的4 + 13 / 5写成后缀就是["4","13","5","/","+"]。约束里有几条能大幅简化实现的保证。第一，表达式总是有效的，也就是不会出现操作数不够、运算符多余或最终剩下多个值的情况，因此不需要写任何错误处理。第二，除数永远不为零，省掉了除零判断。第三，整数除法要求向零截断，例如
7 / -3结果是-2而不是-3——Java 和 Go 的整数除法本身就是向零截断，正好与题意一致，不必额外处理。第四，答案和所有中间结果都保证能用 32 位整数表示，所以不需要long。边界上要注意：数字可能是负数，字符串形如
"-11"，判断「是不是运算符」时不能只看首字符是不是符号；表达式可能只有一个数字，此时答案就是它本身；运算符两侧的操作数顺序对减法和除法至关重要。
解法：栈模拟表达式求值
核心思路
后缀表达式已经把运算优先级编码在 token 顺序中：读到运算符时，它需要的两个子表达式一定已经计算完成。最近完成的结果最先被使用，正好符合栈的后进先出特性。
扫描过程中维护不变量：栈中从底到顶保存“已读 token 形成、但尚未被后续运算符合并”的子表达式结果。数字直接入栈；遇到运算符时弹出两个数，先弹出的是右操作数，后弹出的是左操作数，计算
left op right后再压栈。有效表达式处理完后，栈中只剩最终答案。减法和除法不满足交换律，左右顺序不能反。题目要求除法向零截断，Java 和 Go 的整数除法正好符合；不要改用向下取整。负数 token（如
"-11"）也不是减号，应按完整字符串识别运算符。
解题步骤
- 建立整数栈，按顺序遍历所有 token。
- 数字转成整数后直接入栈。
- 遇到运算符时，依次弹出
right、left，计算left op right并把结果压回栈。- 扫描结束后返回栈顶唯一元素。
例如
["4","13","5","/","+"]：先得到栈[4,13,5]；/取出right=5、left=13，压入13/5=2；随后计算4+2=6。
代码实现
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<>();
for (String token : tokens) {
switch (token) {
case "+":
case "-":
case "*":
case "/":
int right = stack.pop();
int left = stack.pop();
int value;
switch (token) {
case "+":
value = left + right;
break;
case "-":
value = left - right;
break;
case "*":
value = left * right;
break;
default:
value = left / right;
}
stack.push(value);
break;
default:
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
}
import "strconv"
func evalRPN(tokens []string) int {
stack := make([]int, 0, len(tokens))
for _, token := range tokens {
switch token {
case "+", "-", "*", "/":
right := stack[len(stack)-1]
left := stack[len(stack)-2]
stack = stack[:len(stack)-2]
value := 0
switch token {
case "+":
value = left + right
case "-":
value = left - right
case "*":
value = left * right
case "/":
value = left / right
}
stack = append(stack, value)
default:
value, _ := strconv.Atoi(token)
stack = append(stack, value)
}
}
return stack[len(stack)-1]
}
复杂度分析
- 时间复杂度：$O(S)$，
S为所有 token 的字符总数；每个字符至多参与一次数字解析，每个 token 只入栈、出栈常数次。- 空间复杂度：$O(n)$，
n为 token 数量，最坏情况下栈中保存线性数量的操作数。
关键点总结
- 后缀表达式不需要处理括号或优先级，运算顺序由输入位置决定。
- 栈顶是右操作数，第二个弹出的数才是左操作数。
- Java、Go 的整数除法向零截断，符合题意。
- 运算符要按完整 token 判断，不能把负数的前导
-当成减法。
易错点总结
- 弹栈顺序写反：
["5","3","-"]会算成3-5，正确结果应为 2。- 使用向下取整的除法：
7/-3按题意应得到-2，不是-3。- 根据首字符判断运算符：
"-11"会被误判为减号。- Go 弹出两个操作数时只缩短一个元素：旧操作数会残留在栈中，破坏后续计算。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 224. 基本计算器 | 困难 | 中缀带括号与一元正负号 |
| 227. 基本计算器 II | 中等 | 无括号但需处理乘除优先级 |
| 772. 基本计算器 III | 困难 | 括号与优先级的完整组合 |
| LCR 036. 逆波兰表达式求值 | 中等 | 同题换皮的后缀求值 |
| 面试题 16.26. 计算器 | 中等 | 从字符串直接解析并求值 |
| 20. 有效的括号 | 简单 | 栈做成对匹配的入门形态 |
| 1006. 笨阶乘 | 中等 | 固定优先级序列的栈式归约 |