说到 LeetCode 里的“基本计算器”Basic Calculator刷过题的人应该都不陌生。它常以 224 和 227 两个题号出现一个带括号只算加减一个不带括号但引入乘除。很多刚刷到这里的同学会觉得这不就是个表达式求值吗堂堂正正写个栈就完事了。可真到动手写的时候会发现符号处理、括号嵌套、连续空格、整数除法截断这些细节任何一个没想清楚代码就会在某个隐蔽的测试用例上翻车。这篇文章我就把这两道题以及它们的“合体版”一次性讲透从解题原理到完整代码再到调试经验全部按我实际手撕过的方式给你梳理一遍。如果你准备面试、准备周赛或者只是想把表达式求值这类题彻底搞明白这篇都值得你静下心看完。1. 基本计算器系列到底在考什么1.1 两个最常见的版本224 与 227先说清楚题目本身。LeetCode 224 题给一个字符串表达式里面包含数字、空格、加号、减号、左括号、右括号没有乘除要求算出最终结果。示例包括1 1 2、 2-1 2 3以及最经典的(1(452)-3)(68) 23。LeetCode 227 题则把括号去掉引入*和/字符串里只有数字、空格、加减乘除。比如32*2 7 3/2 1。注意这里除法是整数除法并且要求向零截断。两个题在 LeetCode 上都属于经典题也常出现在“热门 100 题”清单里。很多人的误区是把它们当成两个独立的题来背实际上面试官经常改一改把两个考点合并成一个“支持括号 四则运算”的通用计算器这就需要你真正理解底层逻辑而不是只背某一题模板。1.2 隐藏考点不只有栈还有“状态机”很多题解一上来就是“用栈”但栈只是一个工具真正的考点在于你能否把“从左到右扫描字符串”这个过程抽象成一个状态机。什么叫状态机简单说就是每读到一个字符你要清楚当前处于什么状态是在解析数字还是刚遇到操作符还是进入了一个括号子表达式。状态不同处理动作完全不同。比如读数字时可能一个多位数需要循环累加读加减号时需要先把上一个已经累积的数字结算掉读左括号时需要把当前结果“存档”等括号里的表达式算完再“读档”。很多人翻车就是因为没有提前梳理清楚这些状态写代码时东补一块西补一块。所以这篇文章我不仅会给你代码还会把每一步的状态迁移讲明白。1.3 为什么题目看着简单写起来容易翻车我见过不少人背了模板一跑测试用例就崩。主要原因有三个第一边界条件太多。空格可能出现在任意位置数字可能是多位的括号可能连续嵌套表达式的开头可能直接是负号。任何一个没考虑到索引越界或者结果错乱都算轻的更怕的是在面试官面前反复改代码印象分直接掉光。第二符号处理容易乱。1 - (2 - 3)这种括号前带减号的式子如果你不知道把“减法看成加负数”的思想很难一次写对。符号不仅仅影响当前数字还可能影响整个括号内的结果。第三优先级没有想清楚。224 只有加减逻辑相对简单227 加入乘除后如果还是像 224 一样每遇到一个符号就立刻结算那么32*2就会算成(32)*210直接错。优先级才是这类题最核心的考点。2. 表达式求值的核心心法2.1 把减法看成“加负数”乘法除法才是真优先级对只包含加减的表达式有一个非常优雅的处理技巧把所有减法都改写成“加上一个负数”。比如3 - 5可以看成3 (-5)-8 4可以看成(-8) 4。这样做的好处是你不再需要真的执行减法只需要维护一个符号位sign当前的这个数到底是加还是减由符号位决定。遇到sign 1遇到-sign -1。最后统一做加法即可。但到了 227这个方法不够用了因为乘除的优先级更高。比如3 2 * 4你必须先算2 * 4 8再加3。如果还像 224 那样遇到就直接把3加进去那么2就必须被“存起来”等看到*和4时再把2取出来和4相乘。这就是栈的用武之地把当前还不急着参与加减运算的操作数暂存起来等更符号确定优先级后再合并。2.2 括号的本质暂停外层先算内层括号的本质是什么可以理解成一个“强制改变计算顺序的隔离区”。当我们扫描到左括号时括号里的内容必须优先算完再和括号外的结果合并。在代码里这个“隔离”用栈来实现遇到左括号把当前已经算出的结果res和当前符号sign压入栈中然后重置res 0、sign 1专心计算括号内的表达式。等遇到右括号说明括号内已经扫描完了此时把括号内的结果和括号前保存的“外层状态”合并起来。这个过程和递归是一样的只不过栈把这个递归过程显式化了。2.3 一句话看懂栈在其中扮演的角色栈就是一个“待办事项暂存区”。224 里栈存的是“外层的累计结果和符号”用于括号返回时恢复现场227 里栈存的是“已经根据优先级合并过的操作数”用于最后统一求和通用计算器里两个栈分别存数字和运算符边扫描边控制优先级。你可以把栈想象成做菜时的中间容器有的食材要提前备好放在碗里等某个动作完成后才能下锅。表达式求值也是一样所有“暂时不能结算”的信息先放进栈里等时机成熟再取出来用。3. LeetCode 224 手把手拆解3.1 完整解决思路单栈符号位224 的解法可以只用一个栈配合res、num、sign三个变量。核心思路是从左到右扫描字符串。遇到数字则累加到num上可能是一个多位数。遇到说明前面的数已经完整把sign * num加到res上然后重置num 0设置sign 1。遇到-同样把sign * num加到res上重置num设置sign -1。遇到(说明要开始一个子表达式。把当前的res和sign压栈然后重置res 0、sign 1开始计算括号内部。遇到)说明子表达式结束。先把num结算到res上然后从栈中弹出之前的符号和res将当前的res乘以之前符号再加上之前的res。最后字符串扫描完再把最后的num结算到res上。这里面最关键的是右括号的处理。因为括号前可能带有负号比如-(23)所以弹出的符号必须和括号内结果相乘。3.2 Python 实现与逐行注释def calculate(self, s: str) - int: res 0 num 0 sign 1 stack [] for ch in s: if ch.isdigit(): num num * 10 int(ch) elif ch : res sign * num num 0 sign 1 elif ch -: res sign * num num 0 sign -1 elif ch (: # 保存外层的结果和符号 stack.append(res) stack.append(sign) res 0 sign 1 elif ch ): # 把括号内最后一个数结算 res sign * num num 0 # 取出括号前的符号 res * stack.pop() # 取出括号前的外部结果 res stack.pop() # 空格直接忽略 res sign * num return res看到elif ch )那里我用了两步先res * stack.pop()取出符号再res stack.pop()取出外部res。顺序很重要因为压栈时先压res再压sign所以出栈时要先弹sign再弹res。如果你压栈顺序写反了这里也需要对应调整。3.3 详细执行演示拿题目里的经典例子(1(452)-3)(68)走一遍初始res 0, num 0, sign 1, stack []。读到(把res0, sign1压栈然后res0, sign1。读到1num1。读到res 0 1*1 1num0sign1。读到(把当前res1和sign1压栈重置res0。读到4num4读到res044num0读到5num5读到res459num0读到2num2。读到)先res sign*num即91*211然后弹出符号1res * 1仍为 11再弹出外部res1res 1得到12。此时(452)的结果 11 已经合入外层的 1变成 12。继续读-先把当前res12留着sign-1读到3num3读到)先res -1*3即9然后弹出外层符号1再弹出外层res1得到10。于是第一个大括号(1(452)-3)的结果是 10。后面(68)同理先加括号内最终得到23。这种走读方式建议你每次手撕完后都在草稿纸上自己推一遍比单纯看代码印象深得多。3.4 复杂度与一些变形注意224 的时间复杂度是 O(n)每个字符最多被处理一次空间复杂度 O(n)因为栈的深度可能达到括号嵌套层数最坏情况下括号全嵌套栈里存的东西和字符串长度相当。如果换成 Java 或 C要注意 int 溢出问题。题目虽然默认输入合法但表达式很长时中间结果可能超过 32 位整数范围稳妥起见可以用long保存res和num最后再转回 int。Python 没有这个烦恼不过面试时你最好主动提一句溢出处理会显得经验老到。4. 从224到227乘除优先级处理4.1 题目差异与思路变化227 去掉了括号但引入了乘除。表面上是简化了实际上对“结算时机”提出了更高要求。224 里遇到或-就可以直接结算当前数字因为加减优先级相同从左到右计算没问题。但 227 里遇到或-时你不能马上结算因为紧跟在后面的可能是乘除。举个例子3 2 * 4读到时如果急着把 3 结算等到后面出现*时2 已经被孤立出来了没法正确处理。正确思路是用pre_op记录当前操作数前面的那个运算符只有当遇到下一个运算符或者到达字符串末尾时才结合pre_op去处理刚才积累的num。如果是加号或减号直接把num或-num压入栈如果是乘号或除号则从栈顶取出一个数和num做完运算后再把结果压回栈里。这样乘除就在入栈之前被提前计算加减的操作数在栈里只做加法。4.2 经典实现栈存操作数 pre_op下面这段代码是我比较推荐的 227 写法def calculate(self, s: str) - int: stack [] num 0 pre_op n len(s) for i, ch in enumerate(s): if ch.isdigit(): num num * 10 int(ch) # 遇到一个非数字且非空格或者到达字符串末尾时统一结算一次 if (not ch.isdigit() and ch ! ) or i n - 1: if pre_op : stack.append(num) elif pre_op -: stack.append(-num) elif pre_op *: stack.append(stack.pop() * num) elif pre_op /: stack.append(int(stack.pop() / num)) pre_op ch num 0 return sum(stack)注意if的触发条件遇到、-、*、/或者已经扫描到最后一个字符。这里为什么要用or i n - 1因为如果表达式以数字结尾大多数情况都是最后一个数字结算依赖这个条件。遇到ch是操作符时才会去处理它左边的那个数字而pre_op记录的是刚刚处理完的那个操作符不是当前这个ch。这个细节一开始容易绕晕多跑几个例子就明白了。4.3 除法截断陷阱227 最大的坑其实是除法。题目要求整数除法并需要向零截断也就是-3 / 2应该等于-1而不是-2。不同语言的除法语义不一样。C 和 Java 中整数除法默认向零截断直接用/就行。但 Python 中//是向下取整-3 // 2会得到-2这不符合要求。所以 Python 代码里要写成int(a / b)先得到浮点数结果再用int()截断小数部分实现向零取整。如果你用 C 写还有另一个隐患stack.pop() / num的结果类型因为栈里通常存long long除法没问题但如果数字定义成intINT_MIN / -1会溢出。虽然这种用例少见但严谨的面试官可能会问怎么处理。4.4 小结解决这两题后的能力提升把 224 和 227 分别掌握了你对栈的使用会有两层理解224 的栈用来做“括号回退”227 的栈用来做“优先级隔离”。当遇到更复杂的表达式求值场景时这两层理解缺一不可。如果你目标是周赛稳定三题那么这两题是你必须做到“手到擒来”的送分基本功。5. 终极扩展加减乘除 括号的通用计算器5.1 能不能直接合并224和227双栈法面试改题最常出现的就是给一个同时包含括号和乘除的表达式让你求值。这时候你没法只用 224 的符号位也没法只用 227 的pre_op。标准做法是双栈一个栈存数字一个栈存运算符。双栈的核心规则只有两条第一遇到运算符op时如果运算符栈顶的运算符优先级不低于当前op就要先把栈顶运算符结算掉再压入当前运算符。比如1 2 - 3读到第二个-时栈顶是优先级不低于-所以先算123再把-压栈这样能保证同优先级按从左到右结合。第二遇到右括号时不断弹出运算符栈并结算直到遇到左括号为止。左括号本身不参与计算直接弹出。“不低于”这个条件非常重要。如果用“高于”对于1 - 2 - 3这种连续同优先级运算会错误地先算右边的2-3导致结果为1 - (-1) 2。我在第一次写通用计算器时就栽在这里。5.2 双栈法完整代码附优先级处理def calculate(s: str) - int: def apply_op(op: str) - None: b nums.pop() a nums.pop() if op : nums.append(a b) elif op -: nums.append(a - b) elif op *: nums.append(a * b) else: # op / nums.append(int(a / b)) def priority(op: str) - int: if op in (, -): return 1 if op in (*, /): return 2 return 0 # 预处理去掉空格处理一元负号 s s.replace( , ) s s.replace((-, (0-) if s.startswith(-): s 0 s nums [] ops [] num 0 has_num False i 0 while i len(s): ch s[i] if ch.isdigit(): num num * 10 int(ch) has_num True else: if has_num: nums.append(num) num 0 has_num False if ch (: ops.append(() elif ch ): # 结算括号内所有运算符 while ops and ops[-1] ! (: apply_op(ops.pop()) ops.pop() # 弹出左括号 elif ch in -*/: # 栈顶优先级 当前优先级先结算 while ops and ops[-1] ! ( and priority(ops[-1]) priority(ch): apply_op(ops.pop()) ops.append(ch) i 1 if has_num: nums.append(num) while ops: apply_op(ops.pop()) return nums[0]这段代码可以处理像10-(23*4)/2这样的复杂表达式。预处理那两行解决了开头负号和括号后负号的问题比如-34会变成0-341-(-2)会变成1-(0-2)。这样后续算法只需要处理二元运算符省掉不少分支判断。5.3 执行示例与易错点算一下10-(23*4)/2扫描到23*4时2入数字栈入符栈3入栈*入栈此时栈顶*优先级高但下一个数未到不能结算4入栈。遇到)开始结算先弹出*计算3*412压回数字栈再弹出计算21214压回数字栈弹出左括号。此时数字栈里有10, 14运算符栈里有-和/其实扫描到)后继续扫描/左边数字已经结算完毕运算符栈当前有-和/。遇到/时因为栈顶是-优先级 1 低于/的 2所以不结算直接压栈。扫描到2后结束最后清栈先弹/计算14/27再弹-计算10-73。结果正确。这个例子里最容易出错的地方是/入栈的时机。如果写成“遇到运算符立刻处理当前数字”会提前把14当成最终结果导致后面除法出错。双栈法的优势恰恰在于运算符只有在满足优先级条件时才会被结算其他时候都在栈里“排队”。5.4 再进一步支持一元负号与更复杂场景上面的预处理已经处理了常见一元负号。如果你想支持表达式中的正号3可以在开头s s.replace((, (0)以及开头正号不过 LeetCode 一般不需要。再进一步还能支持幂运算^只要把优先级表扩展并在apply_op里加一个分支即可。掌握双栈法后这些扩展其实就是加配置的事情。6. 刷题现场常见问题与排查技巧6.1 空格和空串别让边界成为翻车点224 和 227 的输入里都可能包含空格。你可以在循环里直接跳过空格字符合比如 224 的代码里遇到空格什么都不做因为空格既不是数字也不是运算符操作数跳过不影响逻辑。227 代码里使用ch ! 作为触发结算的判断条件也能正确处理空格。空字符串是另一个边界。题目通常保证输入至少有一个数字但如果你在本地自测最好加上if not s: return 0这样的防御性代码至少能避免索引越界。6.2 负数/连续符号开头和括号后面的负号224 因为有sign变量负号天然好处理。但 227 和通用计算器里如果表达式以负号开头比如-34按照普通逻辑扫描到-时会把pre_op设为-但此时num还是 0处理结果其实也正确因为0 - 3相当于-3。不过为了统一我还是建议按通用计算器的预处理好这样代码分支更少。括号后面的负号尤其危险比如1-(-2)。如果不处理遇到(后紧跟着-通用计算器会尝试压入这个-但数字栈里没有左操作数运行时就会报错。我的预处理s.replace((-, (0-)能干净解决这个问题。6.3 除法、溢出和整数范围Python 里要特别注意除法的向零截断这在上文说过。C 里若栈用long long最后返回(int)res即可。面试时提到“我用了 long long 来避免中间溢出”这是一个很加分的细节说明你考虑过真实世界计算器的鲁棒性。还有一个隐含边界除数为 0。LeetCode 的测试用例一般不会出现但你可以快速判断如果b 0按题目约定无需处理但在实际工程中应该抛异常或做保护。面试时可以说一句“这里默认输入合法如果需要我可以加个判断”。6.4 调试技巧打点输出栈状态我第一次写通用计算器时被一个优先级 bug 卡了很久。后来养成了一个习惯在任何会修改栈的步骤前后打印当前nums和ops。比如在apply_op调用前加print(apply, op, before:, nums, ops)运行一个复杂表达式栈的变化路径一目了然。举个例子输入1-2-3如果优先级判断写错成“高于”而不是“不低于”你会看到第二次遇到-时没有立刻执行1-2而是把第二个-压栈最终清栈时先算2-3-1再算1-(-1)2结果错误。通过打印栈你可以在几秒钟内定位问题。7. 面试与实战中的几点个人体会7.1 先讲思路比快速写代码更重要面试的时候不要一上来就敲键盘。先跟面试官说清楚我打算把减法统一成加负数用符号位处理括号乘除优先级靠栈的延迟结算。这短短几句话能瞬间让面试官知道你不是在背题而是真的懂原理。很多候选人代码写得飞快最后却因为思路混乱被挂就是忽略了“先思考后动手”这个环节。以 224 为例你可以先画一个状态表当前字符是数字、、-、(、)时分别执行什么操作更新哪些变量。这个状态表一出来代码几乎就是对表抄。面试官最喜欢看到的就是这种条理。7.2 测试用例怎么选覆盖各种运算符组合你自己刷题时不要只跑题目给的示例。建议准备一套“必测用例”1 1基础加法。 2-1 2 空格夹杂。(1(452)-3)(68)多层括号和负数。32*2乘法优先级。 3/2 整数除法。-34开头负号。1-(-2)括号后负号。1-2-3同优先级左结合。10-(23*4)/2综合场景。如果这些用例全部通过你的解法大概率是稳的。这套用例我每次手撕计算器之前都会过一遍成本极低收益非常高。7.3 这题还能怎么扩展基本计算器系列看起来是栈的基础题但背后的“状态机 优先级”思想可以辐射到很多地方比如逆波兰表达式、表达式树、命令行解析器、SQL 条件解析等等。甚至周赛里偶尔出现的“带变量的表达式求值”本质上也是在这个框架上加一个变量环境。你把 224、227、通用计算器这三层打穿之后以后遇到任何字符串解析类问题都会比别人多一个思考维度。我个人在实际操作中的体会是这种题一定要在纸上至少手动跑一遍完整流程不能只看题解就以为自己会了。栈里哪个数先弹出、符号位应该乘在哪里、同优先级为什么要先算左边这些细节只有亲手推过才会真正变成自己的东西。希望这篇拆解能帮你少走几步弯路。