力扣227这道题在“剑斩OFFER”这条路上算是一个绕不过去的坎儿。它挂在“栈”这个标签下面难度标着中等但每年栽在它手上的候选人比很多困难题都多。原因很简单它不是考你背没背过模板而是考你能不能干净利落地处理“运算符优先级”这个看似基础、实则全是细节的问题。我经常跟人说这道题做得好不好几乎能直接看出一个人写代码的“手稳不稳”。这道题叫基本计算机II算是一个系列题。它前面有只带加减和括号的基本计算机I后面有加减乘除带括号全都要的基本计算机III。227这个版本的位置特别微妙它去掉了括号但引入了乘除。括号是显式的嵌套结构而乘除是隐式的优先级结构——很多人一遇到“隐式优先级”就不知道怎么用代码表达了所以这道题非常考验对“状态”的理解。这篇文章我会从题目本质开始拆讲清楚为什么用栈、栈里到底存什么、什么时候结算再给出可复现的完整代码和面试里真实会遇到的边界情况。无论你是刚开始刷题的新手还是准备跳槽想快速过一遍高频题的老手这题吃透了后面224、772甚至更复杂的表达式解析都是一个套路往下延展的事。顺便说一句“暴力美学”这个词用在这题上再合适不过。它没有花哨的算法没有诡异的优化就是一次扫描、一个栈、几个变量靠最朴素的方式把四则运算的优先级安排得明明白白。但这种朴素并不简单里面的判断时机、边界处理、语言差异全是经验的累积。下面我一点点讲。1. 题目在考什么先把这个题看穿1.1 输入输出与题目的“潜台词”原题描述大概是这样的给你一个字符串表达式s只包含非负整数、、-、*、/和空格请你实现一个基本计算器来计算它的值。整数除法向零截断并且不允许用eval()这种内置的数学表达式求值方法。示例很简洁输入: 32*2 输出: 7 输入: 3/2 输出: 1 输入: 35 / 2 输出: 5先别急着觉得简单。注意题目里说的“只包含非负整数”意思是数字本身不带符号但表达式里通过-运算符是可以产生负数中间结果的比如3 - 5 * 2。另外实际面试和测试用例里偶尔会出现开头就是负号的表达式比如-32*2虽然描述没直接说支持但一个健壮的解法应该能兜住这种情况。我后面第4章会专门讲。还有一个关键点整数除法向零截断。这意味着-3/2的结果是-1而不是-2。很多语言自带的行为跟这个不一致这是一个重量级的坑后面单独展开。1.2 “暴力美学”到底美在哪我见过不少解法有人一上来就想用递归下降有人想转后缀表达式还有人直接想把字符串按拆开再处理。这些思路都没错但对于227这种规模的问题都有点“杀鸡用牛刀”。真正的核心难点只有一句话乘除法的优先级高于加减法所以遇到乘除不能立刻和后边的数做运算但你也不能不运算否则优先级就乱了。怎么解决最朴素的思路就是先把所有乘除法“消化”掉让表达式退化成只剩加减法然后一次性求和。举个例子3 2 * 2 - 6 / 3这个表达式如果从前往后傻算算3 2 5再算5 * 2 10再算10 - 6 4再算4 / 3 1结果是1但正确答案是3 4 - 2 5。错在哪错在2*2和6/3这两个“乘法项”被强行拆开参与加减了。正确做法是先把2*24、6/32算出来把表达式变成3 4 - 2再从左到右算。所以这个题的“暴力美学”就是我们不去构建什么语法树就用一次线性扫描配合一个栈把一个混合表达式拆解成若干个“最终可加的项”。这种“把复杂问题拆成同构子问题、然后老实扫描”的思路就是典型的算法暴力美学——它不炫技但干净、正确、好证明。2. 方案选型为什么是栈而不是别的2.1 三种主流思路的对比在讨论具体代码前我先把三种可行方案放在一张表里大家有个全局认识。这三种方案我都实际写过各有适用场景。方案核心思路空间复杂度写起来难度适用场景单栈 延迟结算栈里只存“最终要加的项”乘除立刻结算加减先压栈O(n)低约30行227题首选面试最推荐双栈数字栈 符号栈一个栈存数字一个存运算符遇到低优先级运算符先算高优先级O(n)中约50行适合扩展成带括号的224/772先展开再求和用正则或手动把乘法展开3*4-3,4再统一加减O(n)中容易出错不推荐边界处理太分散2.2 单栈“延迟结算”的核心思想我选方案一也就是“单栈 延迟结算”。它的逻辑可以这么理解把整个表达式拆成若干个“加法项”每个加法项在进入栈之前已经被乘除法处理过了。还是拿3 2 * 2 - 6 / 3举例。我们希望在扫描结束后栈里变成这样[3, 4, -2]然后sum(stack) 5就是答案。注意栈里的每一项都是“最终可以直接相加的数”乘除法的影响已经被提前算进去了。那怎么做到呢关键是记住当前数字前面的那个运算符。我用一个变量preOp存它如果preOp是说明当前数字是独立的加法项直接压栈如果preOp是-说明当前数字是负数加法项压-num如果preOp是*说明当前数字要和栈顶项做乘法把栈顶pop出来乘完再压回去如果preOp是/同理栈顶和当前数字做整除后压回。这里有一个非常关键的理解点当我们看到一个运算符时上一轮的数字已经完整读完了此时要结算的是“上一个运算符”的作用而不是当前这个运算符。很多人的代码写错就是因为在运算符这里用了当前符号去操作而不是用缓存的preOp。用生活比喻来说preOp就像你排队时的“前一个人手里的票据”等轮到你结算时决定你付多少钱的是那张旧票据而不是你身后那个人的表情。等结算完再把新票据递给你身后的人。2.3 为什么不是双栈双栈方案确实更通用它能处理括号和各种优先级。但对227来说它有点浪费因为没有括号运算符的层级只有两层加减、乘除我们用一个符号变量就能记住“当前运算符”完全没有必要维护一个符号栈。用一个栈存数加上一个变量存符号逻辑最简也最不容易出错。面试时如果遇到这题我建议就直接写单栈方案写完可以补一句“如果加上括号我会用双栈或递归来处理”这样既显得熟练又为后续的扩展题埋了伏笔。3. 手把手拆解实现从伪代码到完整代码3.1 扫描状态机的关键变量这个解法的本质是一个小型状态机。核心变量如下stack存所有待相加的项。num当前正在拼接的整数。注意数字可能有多位比如123所以要num num * 10 digit累加。preOp当前数字之前最近的那个运算符初始化为。初始化为加号的巧妙之处在于表达式开头的第一个数字会被当成“num”压栈不会出错。一个判断“触发结算”的条件遇到运算符或者扫到了字符串末尾。注意空格是要跳过的它不改变任何状态。很多第一次写的人会在空格上翻车比如把空格当运算符触发一次结算导致逻辑错乱。我的写法是ch既不是数字也不是空格才触发结算或者当前是最后一位也必须触发结算因为数字读到末尾了必须把最后一项入栈。3.2 Python 完整实现与逐行注释我先把Python版本贴出来这个版本最干净适合理解核心思想。class Solution: def calculate(self, s: str) - int: stack [] num 0 # 当前正在累积的数字 pre_op # 当前数字之前的运算符初始化为 s s.replace( , ) # 去掉所有空格 for i, ch in enumerate(s): if ch.isdigit(): num num * 10 int(ch) # 处理多位数 # 触发结算遇到运算符或者已经扫到最后一个字符 if (not ch.isdigit()) or (i len(s) - 1): if pre_op : stack.append(num) elif pre_op -: stack.append(-num) elif pre_op *: stack.append(stack.pop() * num) elif pre_op /: # 注意这里用 int() 向零截断不能直接用 // stack.append(int(stack.pop() / num)) # 结算完成后更新运算符为当前字符数字清零 pre_op ch num 0 return sum(stack)这段代码的精华在第10行到第20行的判断。我逐条解释当遇到或-时它结算的是preOp对应的那个数字。比如表达式3 2 * 2扫描到时num还是3preOp是于是把3压栈。然后preOp更新为。当遇到*或/时它结算的仍然是preOp对应的数字只不过preOp是*或/所以会和栈顶做乘除。比如继续扫描2 * 2遇到*时num是2preOp是把2压栈preOp更新为*。接着扫描到末尾时num是2preOp是*触发结算stack.pop()取出22 * 2 4压栈。最终栈是[3, 4]sum(stack) 7。这里有个细节if (not ch.isdigit()) or (i len(s) - 1)这个条件的or后面的部分是给末尾数字用的。因为表达式最后通常是个数字没有运算符来触发结算必须在循环结束后手动结算而我的写法是在循环体内用i len(s)-1来触发这样可以保持num计算和结算在同一个循环里逻辑内聚。3.3 C 实现与数据类型注意面试场景很多是C我也把C版本贴出来。注意C里字符判断要用isdigit()并且需要包含cctype头文件不过力扣环境通常已经隐式包含了。class Solution { public: int calculate(string s) { vectorint stk; // 用vector模拟栈方便遍历 int num 0; char preOp ; for (int i 0; i s.size(); i) { if (isdigit(s[i])) { num num * 10 (s[i] - 0); } // 遇到运算符非数字且非空格或者已经是最后一个字符 if ((!isdigit(s[i]) s[i] ! ) || i s.size() - 1) { switch (preOp) { case : stk.push_back(num); break; case -: stk.push_back(-num); break; case *: stk.back() * num; break; case /: stk.back() / num; break; } preOp s[i]; num 0; } } int ans 0; for (int x : stk) ans x; return ans; } };注意这里我用vectorint而不是stackint纯粹是因为vector可以用stk.back()直接操作栈顶且最后求和方便。你完全可以用stackint逻辑一样。C版本里有个需要关注的点stk.back() / num当num是负数时C的整数除法是向零截断的这正好符合题目要求。但如果你习惯写stk.back() / num看到负号时要意识到这里没有歧义。真的没有歧义有的Python里就有我第4章细说。3.4 一个更“暴力”的变体先展开所有项再求和能理解上面栈的写法后我再教你一个可以拿来“炫技”的变体。既然栈里存的是“最终可加的项”那其实我们不一定用栈可以用两个变量分别维护current当前连续的乘除链条的结果total已经确定下来的加减项总和。扫描时遇到或-把current累加到total然后根据符号重置current遇到*或/更新current继续乘除链条。因为我们已经不需要保留中间项这个写法空间复杂度可以降到O(1)。但它的代码可读性比栈版本差一些需要非常仔细地维护current的正负号。我个人建议面试写栈版本因为好解释私下练习时可以写写O(1)版本加深对状态的理解。O(1)版本的思路大概是def calculate(s: str) - int: s s.replace( , ) total 0 current 0 num 0 pre_op for i, ch in enumerate(s): if ch.isdigit(): num num * 10 int(ch) if (not ch.isdigit()) or (i len(s) - 1): if pre_op : total current current num elif pre_op -: total current current -num elif pre_op *: current * num elif pre_op /: current int(current / num) pre_op ch num 0 return total current注意这个写法里遇到/-时是把current累加到total然后重新给current赋值。它的正确性依赖一个微妙的逻辑total是“已经和当前乘除链条相隔断”的部分current是当前正在累积的乘除项。理解这个版本的代码你会对“栈里到底存了什么”有更深的认识。4. 实战踩坑边界条件与排查实录4.1 表达式开头就是负号题目说“只包含非负整数”但真实测试用例里-32*2这种情况偶尔会出现。你可能会问这符合题意吗严格说不太符合但题目的“有效表达式”验证时力扣官方数据是允许这种输入的因为它是合法表达式。所以一个健壮的解法必须兼容。我的代码为什么天然兼容因为preOp初始化为遇到第一个字符-时num是0会先按0压栈然后把preOp更新为-。接下来读到3到末尾或遇到下一个运算符时结算preOp是-会把-3压栈。最终结果正确。这个“初始化为、把0压栈”的设计简单又优雅。你不需要单独判断开头负号状态机会自动消化。这是我在实际调试中觉得最巧妙的一个细节也是面试时可以主动提一句的亮点。4.2 除法截断方向C/Java/Python的隐藏差异这是227题最大的语言陷阱。整数除法“向零截断”的意思是-3/2的结果是-1而不是-2。C 和 Java 的整数除法本身就是向零截断所以stk.back() / num直接写就行Python 的//运算符是向下取整也就是向负无穷方向取整。-3 // 2 -2不符合题意但 Python 的int(-3 / 2)是先做浮点除法得到-1.5再int()向零截断得到-1符合题意。所以我在Python代码里特意写的int(stack.pop() / num)而不是stack.pop() // num。就是这一行的差异坑了无数人。用Python刷题的同学一定要记住这个区别。只要你用的是int(a / b)那就和C的整数除法行为完全一致。顺带一提如果面试官追问“除数为0怎么办”你回答“题目保证不会出现但防御性代码里可以加个判断抛异常”就行。227题的数据不会出现除零不要过度设计。4.3 数字溢出与累加陷阱力扣的整数范围限制在int32位内但有一个隐患在拼接多位数num num * 10 digit的时候如果表达式里有一个超过int范围的大数累加过程可能溢出。力扣官方测试一般把这个范围卡得很好但在面试手写白板时你可以主动提到“把num和栈里的元素声明为long long更安全”。C里用vectorlong longPython里因为int无上限所以不用管。另一个真实的溢出场景是stack.pop() * num两个大数相乘中间结果可能超过int范围。C里如果栈是int这里就爆了。所以我在C代码里会写vectorlong long stk最后再转成int返回。这是一种非常实用的工程习惯。4.4 空格与“最后一个字符”的判空陷阱空格在表达式里可能出现任意位置包括开头、结尾、数字和运算符之间。我的处理方式是在Python里先s.replace( , )统一干掉C里则是在判断条件里加一个s[i] ! 。两种方法都行但要注意如果你用replace干掉空格那么“遇到运算符触发结算”的条件就是not ch.isdigit()如果你不干掉空格那么触发条件必须写成(!isdigit(s[i]) s[i] ! )否则空格也会触发一次假的结算。还有最后一个字符的场景。表达式末尾没有运算符只有数字比如12扫到2之后循环结束如果不额外触发一次结算2就永远不会入栈。我的写法是i len(s)-1时强制触发结算这样循环结束前刚好把最后一项处理完。很多人的第一版代码漏掉这个导致结果少了最后一项这是最常见的“手误”。4.5 常见问题速查表问题现象根本原因解决方案结果总是少了最后一项末尾数字没有触发结算在i len(s)-1时强制结算空格导致计算错乱空格被当成了运算符触发结算先去掉空格或用s[i] ! 排除负数除法结果不对Python//向下取整用int(a / b)或math.trunc(a / b)乘除运算结果偏大stack.pop() * num溢出栈声明为long long表达式以-开头结果错误没有处理负号开头的状态preOp初始化为状态机自动处理中间结果被错误地先算了加减在乘除链条中遇到就把current加进total理解栈的“延迟结算”加减法只是切分项的策略这些坑每一个都是我实际写代码时踩过的。尤其是最后一个“先算加减”的逻辑错误初学时很容易犯。我打个比方你在算1 2 * 3如果一看到就把12先记成3后面就只能处理3*3了答案直接变9。正确做法是看到只切分“加法项”2*3这个项还在独立生长等乘除算完才并入总和。这就是“延迟结算”的直觉来源。5. 从227到整个计算器家族面试变体和延伸5.1 加括号的224套路向上延伸如果面试官在227之后追问“那如果表达式里有括号怎么办”这就是224题了。224的表达式中只有、-和括号没有乘除。它的解法可以在227的基础上扩展遇到左括号(把当前栈和符号压进“现场保存区”然后重新开始一个新的状态机遇到右括号)把当前括号内的所有项求和然后弹出保存的现场恢复外部状态。用一个stackpairint, int或者两个栈来保存“现场”逻辑就清晰了。227里我们只用了一个preOp变量扩展到括号场景时preOp变成了一个栈——因为括号嵌套时每个层级的运算符状态都需要暂时保存。这就是双栈方案能通吃的根本原因。你可以自己在纸上推一遍(1(452)-3)(68)尝试用两个栈模拟跑通之后你对224的理解会非常深。核心还是那四个字延迟结算。5.2 通用表达式求值框架调度场算法如果你想把计算器做成一个真正通用的东西那就得提一提调度场算法Shunting-yard algorithm。它的作用是把中缀表达式我们平时写的3 4 * 2转换成后缀表达式RPN即3 4 2 * 然后再用一个简单的栈求值。这个算法是227的“完全体”。它用两个栈一个存运算符一个存输出结果。规则是数字直接输出运算符要跟栈顶比较优先级如果栈顶优先级不低于当前运算符就先弹出栈顶。遇到左括号强制压栈右括号弹出到左括号为止。为什么我在227里不直接教你调度场因为在只有两级优先级、没有括号的场景里它的基础设施太重了。但理解了227的preOp之后你再看调度场算法会豁然开朗227的preOp就是调度场里“运算符栈”只剩一个元素的退化版本。从简单到复杂学习曲线平滑得多。5.3 工程上的正确姿势为什么不能信eval最后说点工程经验。在面试中题目明确禁止eval()这是因为内置求值函数把脏活都干了考不出思维能力。但在真实项目里我也不会建议用eval()或动态执行字符串表达式原因有三安全表达式字符串直接作为代码执行注入风险极大性能动态解析没有预热优化高频调用时性能不稳可控性你无法精确控制错误类型、精度模式和运算规则。如果真的要在生产环境处理用户输入的公式我一般会用以下方式之一成熟的表达式解析库如 Python 的asteval、JS 的expr-eval先把表达式解析成 AST抽象语法树再遍历求值用调度场转 RPN再在自己的求值器里跑。用227题学到的“延迟结算”思想去理解AST求值你会发现底层的组织方式惊人地一致每个节点要么是叶子数字要么是运算符节点运算符节点的子节点算完再应用运算符。我们手写的227代码本质就是构建了一个非常扁平的AST然后用栈把它拍平了。6. 最后再说两句体己话我在面试别人时经常出这道题能看到两类明显不同的候选人。一类是背过题解默写得很流畅但你换个输入、加个负数、改一下除法语义他就懵了。另一类是从状态机层面理解这题能给你讲明白为什么preOp要初始化为加号、为什么除法要用int()向零截断这种人哪怕默写速度慢一点我也更愿意给过。所以这个题我真心建议你不要急着背代码而是先在纸上手推几个用例32*2看乘除怎么延迟 3/2 看空格怎么处理1-11看加减交替时栈的变化-32看负号开头怎么兜底0-2147483648看溢出边界。把这五个用例在纸上跑一遍栈的每一步变化都画出来你对“状态机”三个字的理解会直接上一个台阶。等你能在白板上一边画栈一边讲清楚preOp的切换时机227这道题就算真正“斩”下来了。下一个遇到 224、772 甚至逆波兰表达式求值你就知道它们全是同一个祖宗变的。这也是我跨了这么多年、刷了几百道题之后越来越觉得值得分享的一条经验面试不考你见过的题多不多考的是你把一个题理解得透不透。
