逆波兰表达式求值

怎样从“求逆波兰表达式 ["2","1","+","3","*"] 的值。”推导出 栈 · 逆波兰，并证明每次状态变化都不会漏掉答案？

中心结论：遇数字入栈;遇运算符弹出两个操作数计算后再入栈。

求逆波兰表达式 ["2","1","+","3","*"] 的值。

在本站主例中，求逆波兰表达式 ["2","1","+","3","*"] 的值。

算法最终需要得到或观察：(2+1)*3 = 9。

每一步重新回看全部历史会重复；栈或队列只保存仍可能影响未来决策的状态。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“栈与队列轨道”，明确答案需要观察什么。
2. 2状态只维护 操作数栈、当前 token、栈深度。
3. 3转移每一步按照 遇数字入栈;遇运算符弹出两个操作数计算后再入栈。
4. 4收尾读取 (2+1)*3 = 9。，并复核边界与复杂度。

入栈/入队的不是所有历史，而是未来仍需要的信息。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：操作数栈、当前 token、栈深度。

这道题就是经典的考察栈的知识的题目。

遇数字入栈;遇运算符弹出两个操作数计算后再入栈。

执行过程中持续维护：操作数栈、当前 token、栈深度。

正确性依赖以下不变量：扫描到任意位置时，栈中保存的是已经解析完成、但还没有被更外层运算符消费的子表达式结果。

面试时可以压缩为：这题用栈。顺序扫描 tokens，遇到数字就转 int 入栈；遇到运算符就弹出两个数，注意第一次弹出的是右操作数，第二次弹出的是左操作数，计算 left op right 后把结果压回栈。逆波兰表达式保证每个运算符出现时，它的两个操作数已经在栈顶，所以不需要处理括号和优先级。最终栈里唯一的元素就是答案。时间 O(n)，空间 O(n)。

落到当前题，执行机制可以压缩为：遇数字入栈;遇运算符弹出两个操作数计算后再入栈。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入求逆波兰表达式 ["2","1","+","3","*"] 的值。 因为：遇数字入栈;遇运算符弹出两个操作数计算后再入栈。
2. 2操作数入栈,运算符弹出两个从左到右扫描。 因为：后缀表达式天然适合栈。
3. 3数字 1 入栈操作数直接压栈。 因为：等待后续运算符使用。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5right=1, left=2,计算 2 + 1 = 3二元运算,结果压栈。 因为：第一次 pop 是 right,第二次 pop 是 left,计算 left op right。
6. 6数字 3 入栈操作数直接压栈。 因为：等待后续运算符使用。
7. 7最终答案 9表达式求值完成。 因为：O(n) 单次扫描。
8. 8收尾与复杂度(2+1)*3 = 9。 因为：时间 O(n) · 空间 O(n)。遇数字入栈;遇运算符弹出两个操作数计算后再入栈。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

import (
	"strconv"
)

func evalRPN(tokens []string) int {
	stack := make([]int, 0, len(tokens))
	for _, token := range tokens {
		v, err := strconv.Atoi(token)
		if err == nil {
			stack = append(stack, v)
		} else {
			num1, num2 := stack[len(stack)-2], stack[len(stack)-1]
			stack = stack[:len(stack)-2]
			switch token {
			case "+":
				stack = append(stack, num1+num2)
			case "-":
				stack = append(stack, num1-num2)
			case "*":
				stack = append(stack, num1*num2)
			case "/":
				stack = append(stack, num1/num2)
			}
		}
	}
	return stack[0]
}

func main() {
    // 1. 主例
    //    输入：mode="rpn", tokens=["2","1","+","3","*"]
    //    期望：(2+1)*3 = 9。
    //
    // 2. 失败 / 未命中
    //    检查：减法和除法顺序：第一次 pop 出来的是右操作数，第二次 pop 出来的是左操作数。right = stack.pop(); left = stack.pop(); result = left op right
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC224 基本计算器；LC227 表达式求值
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意求逆波兰表达式 ["2","1","+","3","*"] 的值。
2. 2重复每一步重新回看全部历史会重复；栈或队列只保存仍可能影响未来决策的状态。
3. 3优化遇数字入栈;遇运算符弹出两个操作数计算后再入栈。
4. 4证明扫描到任意位置时，栈中保存的是已经解析完成、但还没有被更外层运算符消费的子表达式结果。
5. 5复杂度时间 O(n)，空间 O(n)