https://leetcode.cn/problems/8Zf90G/description/
一、题目解析
1.1 题意
逆波兰表达式（Reverse Polish Notation），说白了就是把运算符写在两个操作数后面。比如中缀 (2+1)*3 写成后缀就是 ["2","1","+","3","*"]——2 1 + 表示 2+1。
逆波兰的好处是没有括号，也不用考虑优先级——顺序本身就编码了计算次序。求值规则只有两条：
- 遇到数字，压入栈。
- 遇到运算符，从栈里弹出两个数，算完把结果压回去。
整个数组扫完，栈里剩下的唯一一个数就是答案。
1.2 示例推演
拿 ["2","1","+","3","*"] 走一遍，对应中缀的 (2+1)*3，答案是 9。
token "2" 数字入栈 栈：[2]token "1" 数字入栈 栈：[2, 1]token "+" 弹出 1、2，算 2+1=3，压回 栈：[3]token "3" 数字入栈 栈：[3, 3]token "*" 弹出 3、3，算 3*3=9，压回 栈：[9]扫完了，栈顶的 9 就是结果。
这里有个细节值得停一下：弹出的第一个数是 1，第二个数是 2，但算的是 2+1 而不是 1+2。
二、栈解法模板
// 通用骨架：扫一遍 token，数字入栈，运算符弹两个算完再压回Deque<Integer> stack = new ArrayDeque<>();for (String token : tokens) { if (isOperator(token)) { int right = stack.pop(); // 先弹出的是右操作数 int left = stack.pop(); // 后弹出的是左操作数 stack.push(calc(left, right, token)); } else { stack.push(Integer.valueOf(token)); }}return stack.peek();两个要点。
一是弹出顺序。栈是后进先出，左操作数比右操作数先入栈，所以出栈时反过来——先出来的是右边那个。
二是运算符怎么判断。最直觉的写法是 if (token.equals("+")) ... else if (token.equals("-")) ...，四个分支堆下来又长又乱，而且"判断它是什么"和"该怎么算"这两件事被拆在了两处。下面这份代码换了个思路。
三、代码详解
3.1 Action 接口
代码里定义了一个只有一个方法的私有接口：
// 约定：a 是左操作数，b 是右操作数private interface Action { int doAction(int a, int b);}然后用 HashMap<String, Action> 把符号和运算绑起来，每种运算用匿名内部类实现。本质就是把"怎么算"封装成一个个对象，用的时候按符号查表取出来——策略模式最朴素的落地方式。
3.2 主循环逻辑
for (String token : tokens) { // 能在表里查到，说明是运算符 if (actions.containsKey(token)) { int a = stack.pop(); // 先弹出，这是右操作数 int b = stack.pop(); // 后弹出，这是左操作数 stack.add(actions.get(token).doAction(b, a)); // 调换回 (左, 右) } else { stack.add(Integer.valueOf(token)); // 数字，直接入栈 }}return stack.peek();doAction(b, a) 这一行是核心。变量名 a 是先 pop 出来的，按 1.2 的推演它是右操作数；b 后 pop，是左操作数。而 Action 接口的语义是 doAction(左, 右)，所以传参必须写成 (b, a)，把两者对调回来。
另外 stack.add(...) 和 stack.push(...) 在 Stack 上是等价的——Stack 继承自 Vector，add 追加到尾部，而 Stack 的栈顶就是尾部。
最后 return stack.peek()，因为表达式合法，扫完必然只剩一个元素。
3.3 完整代码
class Solution { // 运算策略接口：约定 a 是左操作数，b 是右操作数 private interface Action { // 运算操作 int doAction(int a, int b); } public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); // 符号 -> 运算实现的映射表，替代 if-else 链 Map<String, Action> actions = new HashMap<>(); actions.put("+", new Action() { @Override public int doAction(int a, int b) { return a + b; } }); actions.put("-", new Action() { @Override public int doAction(int a, int b) { return a - b; } }); actions.put("*", new Action() { @Override public int doAction(int a, int b) { return a * b; } }); actions.put("/", new Action() { @Override public int doAction(int a, int b) { // int 除法自动向零截断 return a / b; } }); for (String token : tokens) { // 查表命中，说明当前 token 是运算符 if (actions.containsKey(token)) { int a = stack.pop(); // 先弹出的是右操作数 int b = stack.pop(); // 后弹出的是左操作数 // 调换回 (左, 右) 的顺序再交给策略计算，结果压回栈 stack.add(actions.get(token).doAction(b, a)); } else { // 否则是数字，转成 Integer 后入栈 stack.add(Integer.valueOf(token)); } } // 表达式合法，扫完栈里只剩最终结果 return stack.peek(); }}四、复杂度分析
时间 O(n)。每个 token 处理一次，栈操作和 HashMap 查表都是 O(1)。数字解析的开销跟位数相关，但位数有上界，当常数看就行。构建 actions 表是固定四次 put，和 n 无关。
空间 O(n)。最坏情况是所有数字都排在表达式前头，栈一口气涨到 n。运算符每次消耗两个数、产出一个，中途栈会缩，但上界还是 O(n)。actions 表只有四个条目，常数空间，不占大头。
本文由 AgentPlanFlow 生成