栈与队列中等1 种解法
#150逆波兰表达式求值
计算有效逆波兰表达式，整数除法向零截断。
#数组#栈#数学
原题
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*'和'/'。 - 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
示例 1：
输入：tokens = ["2","1","+","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = ["4","13","5","/","+"] 输出：6 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] 输出：22 解释：该算式转化为常见的中缀算术表达式为： ((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
提示：
1 <= tokens.length <= 104tokens[i]是一个算符（"+"、"-"、"*"或"/"），或是在范围[-200, 200]内的一个整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式，如
( 1 + 2 ) * ( 3 + 4 )。 - 该算式的逆波兰表达式写法为
( ( 1 2 + ) ( 3 4 + ) * )。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成
1 2 + 3 4 + *也可以依据次序计算出正确结果。 - 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
解题主线
- 遇到数字入栈；遇到运算符时先弹出右操作数，再弹出左操作数。
解法 1：操作数栈
数字压栈，运算符消费栈顶两个操作数并把结果压回。
-
时间复杂度： O(n)
-
空间复杂度： O(n)
import java.util.ArrayDeque;
import java.util.Deque;
final class Solution {
public int evalRPN(String[] tokens) {
// 栈始终保存已扫描前缀中尚未被运算符消费的中间结果。
Deque<Integer> operands = new ArrayDeque<>();
for (String token : tokens) {
if (!isOperator(token)) {
operands.push(Integer.parseInt(token));
continue;
}
// 栈顶先弹出的是右操作数，减法和除法不能颠倒二者顺序。
int right = operands.pop();
int left = operands.pop();
int value = switch (token) {
case "+" -> left + right;
case "-" -> left - right;
case "*" -> left * right;
case "/" -> left / right;
default -> throw new IllegalStateException("Unexpected operator");
};
operands.push(value);
}
return operands.pop();
}
private boolean isOperator(String token) {
return token.length() == 1 && "+-*/".indexOf(token.charAt(0)) >= 0;
}
}实现提示
- 修复减法、除法的左右操作数顺序，并移除会跨调用残留的实例栈。
边界与易错点
- 减法和除法不可交换：旧实现使用 num1-num2、num1/num2，左右操作数颠倒。
- 栈必须是方法内局部状态，否则同一实例多次调用可能相互污染。
- 负数 token 不是减号运算符，应按完整字符串判断。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
medium/Q150_evalRPN.java