1. 题目到底在考什么为什么要死磕这一题力扣150这道“逆波兰表达式求值”在热题100和刷题攻略里出现的频率相当高。我第一次刷的时候其实有点不以为然觉得无非就是给一个后缀表达式拿栈算一遍就完了撑死十几分钟的事。但真正把它吃透之后我意识到这题远不止“会写代码”这么简单——它牵扯到表达式解析、栈的时机控制、异常输入防御甚至是你后续做计算器系列题目比如力扣224、227的地基。先给不熟悉的朋友补个脑子逆波兰表达式也叫后缀表达式就是把运算符写在操作数后面。比如我们平时写的(a b) * c转成逆波兰就是a b c *。它的特点是不需要括号来标识优先级只要你遵守“从左到右扫描遇到操作数就压栈遇到运算符就弹出两个数计算再把结果压回去”这个规则就能严格算出正确结果。力扣150给的输入是字符串数组比如[2,1,,3,*]要求返回一个整数。这道题在LeetCode上被标为中等难度但从数据结构和算法设计角度看它考察的其实是一个非常经典且高频的状态机场景线性扫描 栈式状态积累。很多人觉得简单是因为它没有复杂的递归和动态规划但真正在面试或实际工程中容易翻车的恰恰是那些看似“无脑”的边界细节。我在实际刷的时候总结了一个观点这一题是检验你是否真正理解“栈的生命周期”的风向标。你如果只背模板遇到合法的逆波兰表达式可以过但如果题目稍微变一下加入除法截断、负数处理甚至非法输入模板就废了。所以这篇文章我不想只给题解而是把它背后的一系列知识点全部拆开揉碎带着你一步一步走到能举一反三的程度。顺便说一句力扣上“逆波兰表达式求值”这道题还有一个隐藏考点就是除法向零截断。很多语言里//Python和Math.floorJavaScript在负数上的表现是不一样的这一点我后面会专门花一节讲因为这是最容易踩的坑没有之一。整体来看这个题的适用人群非常广正在准备面试的、刚开始刷力扣热题100的、或者在企业里需要自己写表达式引擎的都能从中收获东西。接下来我直接进入正题先聊聊为什么这道题要选择“栈”这个方案以及它的核心设计思路到底是怎么推出来的。2. 核心思路拆解为什么非要用栈优先级去哪了2.1 后缀表达式的天然结构决定了“栈”是最优解很多初学者会问我能不能用递归能不能用两个数组一个存数一个存符号能不能先用中缀转后缀再算答案是你当然可以但全都不是最优解。逆波兰表达式的最大特点就是“运算符紧跟其后”它本身就是一种消除回溯需求的线性表达。我们来想象一下手动计算的过程从左往右看看到数字就先记下来暂时不知道它后面会跟什么运算符看到运算符的时候你需要的是“最近记下来的两个数”。这种“最近记下来”的数据结构天然就是栈。栈的先进后出特性恰好保证了你能拿到“最近的两个操作数”并且顺序不会乱。这就是为什么几乎所有教科书和题解都会选择栈来实现。不是栈“恰好能用”而是逆波兰表达式的定义本身就定义了栈的使用方式。你如果不信可以试着自己用递归去解析一棵表达式树你会发现你其实是在手动模拟一个调用栈那还不如直接用栈来得干脆。我在给新手讲的时候喜欢打一个比方栈就像一个叠盘子的弹簧架后放上去的盘子永远在最上面取的时候也永远先取最上面。后缀表达式里的数字就是盘子运算符就是“把最上面两个盘子拿下来算出一个新盘子再放回去”的动作。你不需要关心底层盘子是什么时候放进去的只需要关心当前顶部的两个盘子。这个抽象一旦建立起来整个算法就只剩下循环和判断了。2.2 为什么中缀转后缀这步可以省掉这里有个很关键的认知力扣150直接给的是后缀表达式也就是说它已经帮你完成了“中缀转后缀”这一步。很多刷到这里的人会突然卡壳怀疑自己是不是要先写一个转换函数。我明确告诉你不需要。力扣给的输入是[2,1,,3,*]它已经是后缀形式了。你只需要“求值”不需要“转换”。但这里引出一个更重要的点如果真的给你一个中缀表达式比如(12)*3你要怎么求值那就需要两个栈一个操作数栈、一个运算符栈还要处理括号和优先级。这就是力扣224“基本计算器”和力扣227“基本计算器 II”干的事。所以我的建议是先把150吃透再去做227最后做224这个顺序是平滑递进的。150里面没有括号、没有优先级比较、没有变量只有“遇到什么做什么”的机械步骤。先把这种机械步骤刻进肌肉记忆后面再加条件判断时你才不会手忙脚乱。还有一个容易被忽略的设计点题目保证了输入一定是合法的逆波兰表达式。这个保证极大简化了代码因为你不用在每次弹栈前判断栈是否为空。但你自己练习或者写工程代码时千万不要默认输入合法防御性编程的习惯从一开始就要养成。我后文会专门给一版带校验的写法。2.3 时间复杂度为什么是 O(n)以及是否还能优化这个题的时间复杂度是 O(n)其中 n 是 token 数组的长度。你只需要从头到尾扫一遍每个 token 最多经历一次压栈和一次弹栈所以均摊下来是线性时间。空间复杂度是 O(n)因为最坏情况下所有 token 都是数字栈里要存下所有操作数。那能不能优化到 O(1) 空间理论上如果入参不是数组而是一个可流式读取的表达式你依然需要一个栈来保存中间结果不可能做到严格 O(1)。有人可能想到用递归展开但递归的调用栈本质上也是 O(n) 空间只是藏在系统栈里了。所以这个题就是“栈”的标准舞台不用追求空间上的花哨优化老老实实写栈就是最优解。3. 手把手实现从读题到提交的完整实操流程3.1 Python 解法最清晰、最接近思路原型的写法先给出我最推荐的 Python 写法因为它最接近我们刚才讲的“栈”的原型思想代码量短且不容易出错from typing import List class Solution: def evalRPN(self, tokens: List[str]) - int: stack [] for token in tokens: if token in {, -, *, /}: b stack.pop() a stack.pop() if token : stack.append(a b) elif token -: stack.append(a - b) elif token *: stack.append(a * b) elif token /: stack.append(int(a / b)) # 关键点向零截断 else: stack.append(int(token)) return stack[0]这个写法的核心逻辑极其简单遇到符号就弹出两个数运算后压回遇到数字就转 int 压栈。整个过程没有任何多余判断因为题目保证了输入合法性。唯一需要注意的就是/分支里的int(a / b)。有人会问为什么不用a // b因为 Python 的//是向下取整对于负数场景会出问题。举个例子-3 // 2在 Python 里结果是-2但逆波兰表达式求值要求向零截断正确结果是-1。而int(-3 / 2)在 Python 里先做浮点除法得到-1.5再用int()截断为-1这样就对了。这里要提醒一个性能相关的细节用token in {, -, *, /}是集合查找平均 O(1)比用token or token -这种一串 or 更优雅也更好扩展。如果为了极致性能可以用if token 这种链路式判断但代码会变得更啰嗦。刷题阶段我更推荐集合写法因为它可读性更好。3.2 JavaScript/TypeScript 解法注意翻转陷阱如果你用 JavaScript 刷题有一个非常隐蔽的坑数组的pop()弹出的是最后一个元素但在语义上先弹出的 b后弹出的才是 a。我们对减法a - b和除法a / b一定要搞清楚顺序。很多初学者在这写反结果就是运算符顺序颠倒答案全错。var evalRPN function (tokens) { const stack []; for (const token of tokens) { if (token || token - || token * || token /) { const b Number(stack.pop()); const a Number(stack.pop()); switch (token) { case : stack.push(a b); break; case -: stack.push(a - b); break; case *: stack.push(a * b); break; case /: stack.push(parseInt(a / b)); break; // 向零截断 default: break; } } else { stack.push(token); // 先存字符串弹出时再转数字 } } return stack[0]; };我写 JS 的时候习惯先不转数字直接 push 字符串弹出时统一用Number()转换。这样写的好处是少一层冗余转换坏处是如果你后面要用严格等于去判断数据类型可能会踩坑。在力扣的环境里无所谓因为最后返回时会转成数字。JS 里的除法截断要用parseInt(a / b)因为Math.floor在负数上同样会向下取整而parseInt会直接丢弃小数部分达到向零截断的效果。这个细节和 Python 的int()一致但如果你用Math.trunc会更明确直接表达“截断”的意图Math.trunc(a / b)语义更清晰推荐使用。3.3 C/Java 风格长整数和负数边界怎么稳C 和 Java 的处理思路和上面一样但有几个细节要额外注意。C 中stoi可以直接把字符串转整数但在-号分支时如果你直接用字符串判断要小心 token 是单个-还是负数-1。好在题目的数字 token 一般不会是单个-所以判断逻辑没问题。C 的分支可以写成#include stack #include vector #include string using namespace std; class Solution { public: int evalRPN(vectorstring tokens) { stackint st; for (const string token : tokens) { if (token || token - || token * || token /) { int b st.top(); st.pop(); int a st.top(); st.pop(); if (token ) st.push(a b); else if (token -) st.push(a - b); else if (token *) st.push(a * b); else if (token /) st.push(a / b); // C 的整数除法本身向零截断 } else { st.push(stoi(token)); } } return st.top(); } };这里有个重要知识点C 和 Java 的整数除法本身就是向零截断所以直接用/就行。也就是说只有 Python 和部分脚本语言会在负数除法上出现“向下取整”的特例C、Java、C# 这些传统强类型语言天然符合题意。这也是为什么很多人在 C 里一遍过在 Python 里反而卡住——真的不是算法问题是语言特性问题。Java 的写法也大同小异用StackInteger或ArrayDequeInteger都可以。我个人推荐ArrayDeque因为Stack是继承了Vector的旧式类性能稍差且带锁开销虽然在这里差距微乎其微但养成用Deque的习惯对后续其他题目更有好处。3.4 防御性写法万一输入不合法怎么办虽然力扣的测试用例保证了输入合法但你自己扩展或面试追问时难免会被问到“如果 token 不合法怎么办”。我建议你在刷题之外准备一份防御性版本这不仅是工程实践的体现也是面试官非常喜欢深挖的点。防御性写法主要做三件事第一空栈时不能 pop第二除数为零时不能除第三非法字符要识别。我给出一个 Python 示例class Solution: def evalRPN(self, tokens: List[str]) - Optional[int]: stack [] operators {, -, *, /} for token in tokens: if token in operators: if len(stack) 2: raise ValueError(表达式不合法操作数不足) b stack.pop() a stack.pop() if token / and b 0: raise ZeroDivisionError(除零错误) if token : stack.append(a b) elif token -: stack.append(a - b) elif token *: stack.append(a * b) else: stack.append(int(a / b)) else: try: stack.append(int(token)) except ValueError: raise ValueError(f非法token: {token}) if len(stack) ! 1: raise ValueError(表达式不合法栈中最终元素不为1) return stack[0]这段代码牺牲了一些可读性但拿到了极高的健壮性。需要注意Optional[int]需要从typing导入我在这里默认你环境已经配好。防御性代码在力扣提交时没必要但在系统设计或本地工具中非常有用。如果你目标是过题用第一版精简代码就够了如果你目标是面试加分建议两手都能拿得出来。4. 常见问题与排查技巧实录那些年我们踩过的坑4.1 最经典负数除法截断方向搞反这个坑我在开头提过这里再展开讲一次因为它绝对值得。力扣题目描述对除法只有一句话“除法运算结果需要向零截断truncate toward zero”。很多人看到这一句就略过了结果在负数除法上栽跟头。打个比方-6 / 4数学上的值约等于-1.5。直接取整有两种策略一种是向更小的方向取得到-2一种是向零的方向取也就是直接丢掉小数部分得到-1。Python 的//是前者力扣要求的是后者。所以int(-6 / 4)在 Python 中得到-1而-6 // 4得到-2一模一样的数据结果天差地别。我的排查小技巧是一旦发现某道题的除法用例在负数上出错优先检查你用的语言的内建除法语义。每门语言在负数除法上的表现都不一样哪怕同属一族也有差异。不要相信直觉直接跑一个负数测试用例验证这是最快的方式。4.2 运算顺序错误a 和 b 谁先谁后第二个高频错误是减法和除法的操作数顺序。栈弹出时后弹出的才是左操作数。举个例子表达式[3,4,-]表示的是3 - 4 -1不是4 - 3 1。如果你先弹出 4 作为 a再弹出 3 作为 b然后计算a - b结果就变成 1 了全错。一个有效的记忆方法第一个弹出的是右操作数第二个弹出的是左操作数。这和我们在数学里写a - b时a 在减号左边、b 在右边是一致的。你只要记住这个顺序减法和除法就不会写错。至于加法和乘法不受影响因为交换律保证结果一致这也是为什么很多人加法乘法不会错一到减法就露馅。4.3 数字转换遗漏忘记把字符串转整数第三种常见错误是把数字 token 直接push进栈但在弹出时没有转整数直接参与数学运算。比如 Python 里1 2的结果是字符串12而不是整数3程序跑起来直接爆炸或得到诡异结果。这种错误特别容易出现在匆忙写代码的时候。我的建议是统一策略要么在压栈时全部转整数要么在弹出时全部转整数绝不在同一个分支里混着来。我个人更推荐压栈时转因为这样后续的运算分支就完全不用操心类型问题。如果压栈时是字符串、弹出时才转逻辑也没错但你要确保每个分支都转了漏一个就完蛋。4.4 用图片式的记忆我把最简单的测试用例贴在脑子里我刷题有个习惯对每一道数据结构经典题都会离线脑补一个最简单的用例来验证代码逻辑。这道题我的基准用例是[1,2,,3,*]等于(1 2) * 3 9。每次写完代码我先在脑子里逐行跑一遍这个用例确认栈的变化过程是[1] - [1,2] - [3] - [3,3] - [9]再提交。这个小习惯帮我拦截了至少一半的低级错误。如果你觉得手动模拟栈比较累也可以用纸笔画一个纵向的栈图从左到右扫描 token遇到数字就往上叠遇到运算符就划掉最上面两个数字、把结果写上去。这种“纸上模拟”的方法看起来很原始但真的能帮你建立对栈结构的肌肉记忆尤其是刚接触栈的读者我强烈推荐至少完整模拟三个用例。4.5 力扣编辑器里的隐藏坑注意函数签名和返回类型最后说一个比较笨但常见的问题力扣的模板函数签名在不同语言里不一样如果你直接从网上复制代码很容易因为函数名、参数类型不匹配而报错。比如 Python 里的List[str]如果没有从typing导入 List在一些老版本的编辑器里会直接报错而新版 Python 其实可以用list[str]内建泛型但力扣默认模板用的是List。我的建议是直接用编辑器里默认的函数签名不要自己重命名。如果你在本地 IDE 调试把完整的from typing import List带上免得跑测试时报 NameError。还有一点在 C 里函数参数是vectorstring如果你不小心写成了传值版本虽然结果对但会有不必要的拷贝开销。这类细节不会影响正确性但面试时暴露出来会显得不够专业。5. 从这一题延伸到力扣热题100栈的家族谱5.1 和“有效的括号”形成对照栈的两种经典用法力扣20“有效的括号”和本题并列刷题攻略前几页两者放在一起看特别有意思。括号匹配题里栈存的是符号本身遇到右括号时弹栈匹配而逆波兰求值题里栈存的是操作数遇到运算符时弹栈计算。一个是“符号栈”一个是“操作数栈”但核心都是“延迟处理直到遇到正确的触发条件”。这告诉我们一个通法只要存在“当前看的是后面信息才能决定当前状态”的情况就应该考虑栈。括号串之所以用栈是因为左括号必须等到对应的右括号出现才能确认匹配逆波兰表达式之所以用栈是因为数字必须等到运算符出现才知道怎么处理。你把这两个题一起刷一遍对“栈”的理解会从“会用”上升到“会选”。5.2 向力扣224/227进阶中缀表达式求值的桥接如果你做了150之后觉得意犹未尽下一个推荐就是力扣227“基本计算器 II”它支持加减乘除和空格但不含括号。这个题的核心就是用两个栈或者“一个栈 一个preSign变量”来处理运算符优先级。当你理解了150里的“遇到运算符弹栈计算”227里“遇到乘除先算、加减入栈”就是它的直接延伸。再往后是力扣224“基本计算器”这个题带括号需要处理左括号时把当前状态压栈、遇到右括号时恢复状态。这个过程本质上就是你在用栈模拟一个子表达式的边界。如果你能带着150的底层思路去理解这三题它们就不再是孤立题目而是一整条“表达式求值”的学习路径。很多热题100的刷题攻略都把这三题拆开排在不同的天但我实际体验下来连着刷的收获远远大于隔开刷。因为它们之间共享同一个心智模型扫描 栈状态切换。每道题只是在这个模型上增加了一个变量150增加了后缀227增加了优先级224增加了括号嵌套。你用同一套框架去套越套越顺。5.3 拿“买股票的最佳时机”对比不同数据结构解决不同问题热词里出现了“力扣 买股票的最佳时机”这题和本题目表面上毫无关系但它能帮你理解“选数据结构之前先看问题本质”。买股票系列的核心是动态规划或者贪心因为你需要维护“到当前位置为止的最小值”和“最大利润”这种状态也不需要“最近两个数”这种信息所以栈在这里不是必需。我的意思是题目选什么数据结构不是由代码风格决定的而是由信息访问模式决定的。这题的访问模式是“取最近的两个数”于是选栈买卖股票是“记录整体最优状态”于是选 DP。你刷多了以后会形成一种直觉一看到“最近”“匹配”“回溯最近状态”就自动想到栈一看到“最优子结构”“状态转移”就想到 DP 或者贪心。这种直觉比记住某道题的模板值钱一万倍。5.4 如何把栈的套路迁移到更多场景栈的套路其实可以归纳为一个“三步走”模板第一步判断你的问题是否涉及“最近元素”或“嵌套结构”第二步确定栈里存什么、什么时候 pop 和 push第三步确认弹出元素的顺序是否满足操作数先后关系。这三步应用到很多问题上都成立比如“每日温度”力扣739、“柱状图中最大的矩形”力扣84。我个人练栈类题目的方法很简单每次遇到一个新题先不看题解先问自己三个问题——栈里存的是什么压栈的触发条件是什么弹栈的触发条件是什么如果这三个问题能在看题后五分钟内答出来那这题基本能直接写出来如果答不出来说明你对题目的抽象还不够强行看题解也只能背模板过两周必忘。6. 写在最后的随手技巧给你一套可以一直用的自查清单我不知道别人怎么刷题但我在完成逆波兰表达式求值这道题后给自己留了一套“栈类题目提交前 30 秒检查清单”后来做所有栈题都用它实测能大幅降低错误率。现在把它一起分享给你。第一步检查运算符分支里是否混淆了左右操作数。重点看减法和除法加法乘法一般没事。第二步检查除法截断方向是否跟题目要求一致。力扣150要求向零截断直接用语言特性确认不要假定所有语言都一样。第三步检查空栈情况。题目保证合法时可以直接 pop但你自己写代码要养成判断习惯。第四步简单用例在脑子里过一遍。我上面说的[1,2,,3,*]以及一个含负数的[-2,3,*]这两个都跑通基本稳了。还有一个更实用的习惯如果你在力扣上刷题遇到超时或者报错先从“运算逻辑”排查再说优化。我见过很多朋友一上来就怀疑复杂度不够高结果最后发现只是 pop 写反了。代码错误绝大多数是逻辑层的低级错误不是复杂度问题。最后聊聊刷题节奏的问题。热题100里的题目密度很大但不要为了“刷完”而刷。我自己的经验是像这样的经典题值得你刷三遍第一遍看题解硬啃第二遍闭卷重写第三遍隔一周再回来快速过一遍。三遍过后这道题才算真正长在你脑子里。逆波兰表达式求值这道题虽然代码短但它代表的数据结构思维是后面几十道题的地基值得你多花这二十分钟。