“表达式求值”这五个字听起来很像数学课本目录里的一节但在数据结构这门课里它几乎每个计算机专业学生都要亲手写一遍。我当年做这个实训项目——基于栈的算术表达式求值算法——前后折腾了整整两个晚上一开始以为难点在“求值”上后来才发现真正的坎是“怎么把人的计算习惯翻译成机器的逻辑”。这篇博客把整套算法从头到尾拆开讲清楚包括中缀表达式转后缀表达式的原理、栈的用法、优先级和括号的处理、边界情况的规避以及我踩过的那些坑。无论你是正在做栈相关实训的同学还是准备面试想巩固基础的开发者亦或是纯粹好奇“计算机到底是怎么算出 12*3 的”这篇内容应该都能让你有所收获。1. 题目拆解与整体设计思路1.1 这个实训项目为什么经典数据结构课的经典题目有很多但“基于栈的算术表达式求值”几乎在每本教材里都占据固定的一席之地这不是没有原因的。它最大的特点是在一个看似简单的需求里把栈、字符串解析、运算符优先级、括号匹配、异常输入处理这些知识点全部串了起来。一句话概括就是题目不大五脏俱全。做一遍这个实训等于同时练了栈的“后进先出”逻辑、字符串的逐字符扫描、多位数拼接、错误输入检测等好几个基本功。尤其对初学者来说这些点单独拿出来都不难但放在一起要能流畅地跑通就需要你对每个细节都有清晰的认识。这也是为什么面试官和出题老师都偏爱这道题。从另一个角度看这道题还是“编译原理”的入门缩影。编译器拿到源代码后的第一步就是词法分析和语法分析而表达式求值恰好就是“词法分析 语法分析 求值”三个步骤的微型简化版。把这道实训吃透你再看编译原理里的语法分析栈、递归下降解析器都会觉得眼熟很多。1.2 先理清三种表达式中缀、后缀、前缀在动手写代码之前必须先搞清楚我们处理的对象是什么。平时我们在纸上写的算式比如1 2 * 3叫中缀表达式。它的特点是运算符写在两个操作数中间符合人类直觉但计算机要计算它并不轻松因为运算符有优先级而且还有括号改变运算顺序机器需要不断回看和判断。后缀表达式又叫逆波兰表达式写法是把运算符放在两个操作数的后面比如1 2 3 * 。它没有括号也没有优先级纠结——因为后缀表达式的运算顺序已经通过顺序固定好了计算时只需要从左往右扫描遇到数字就入栈遇到运算符就弹出两个数字运算再把结果压回去。整个过程是纯机械的非常适合计算机执行。前缀表达式则把运算符放在最前面比如 1 * 2 3它同样是无括号无歧义的但在实际工程和教学中用得相对少一些。这里要特别强调一个常见误区很多人以为“写一个表达式求值程序”就是要直接模拟人脑的计算过程在中缀表达式上边扫描边运算。这当然可行但实现起来优先级、括号、回退处理非常绕。更简单、更工程化的思路是先转换成没有二义性的后缀表达式再统一计算。1.3 两步走到底好在哪里我当时面临两个方案犹豫了很久。方案 A 是双栈直接求值一个栈存操作数一个栈存运算符边扫描边根据优先级决定“是压栈还是先算一步”。这个方案思路直接但实现时要格外小心因为扫描位置、运算符栈顶、操作数栈的弹出时机互相制约一旦出错很难定位问题。方案 B 就是今天要讲的“中缀转后缀 后缀求值”。第一步只负责把中缀表达式重排成后缀形式第二步只负责机械求值。两个步骤职责单一各自可以独立测试出问题时也很容易定位后缀结果不对问题在转换阶段后缀正确但最终结果错问题在求值阶段。我在实训中最终选了方案 B最重要的原因就是可调试性。你能在中间打印出后缀表达式一眼看过去就知道转换有没有问题。对于初学者来说这比在双栈算法里反复脑补状态要友好得多。当然方案 A 也并非一无是处。它更适合“表达式流式输入、需要边读边算”的场景比如某些计算器或实时计算引擎。但针对课程实训这种“输入完整字符串输出结果”的典型需求两步走更稳妥代码也更简洁直观。2. 核心数据结构与算法原理2.1 栈天生适配表达式的结构在具体看代码之前我想先聊清楚一个问题为什么偏偏是栈栈的结构特点可以用“自助餐叠盘子”来理解新盘子总是放在最上面取的时候也总是从最上面拿。这种“后进先出”的特性恰好对应了表达式求值里一个关键矛盾——运算符的读到顺序和运算顺序并不一致。比如1 2 * 3我们读到的顺序是先看到再看到*。但按照运算优先级*要先于计算。也就是说虽然先读到却要等*算完之后才能发挥作用。这个时候我们没办法立刻决定要不要算1 2只能把先“挂起”放在一边等后面出现了更高优先级的运算符时再决定是否把挂起的运算符取出执行。“先挂起、后取出”就是典型的栈操作。所以表达式求值和栈的搭配不是偶然的而是从“优先级倒置”这个根本矛盾里天然推导出来的。理解了这一点你就不会去纠结“要不要背下这段代码”而是能自然想到“这种场景就该用栈”。2.2 运算符优先级表与结合性规则计算机处理优先级最直白的做法就是查表。我们需要给每个运算符设定一个等级然后扫描表达式时把当前运算符和栈顶运算符做比较。运算符含义优先级结合性 -加减1左结合* / %乘除取模2左结合^幂运算3右结合( )括号最高—优先级数字越大代表先算。括号不参与后缀表达式的输出它在转换中只用作控制栈的“标记”。结合性是什么意思呢减法从左往右算1 - 2 - 3等于(1 - 2) - 3这叫左结合。幂运算恰好相反数学上2 ^ 3 ^ 2指的是2^(3^2)也就是从右往左算这叫右结合。这个区别非常重要它就是中缀转后缀时“什么时候弹出栈顶运算符”的关键依据。左结合的运算符遇到栈顶优先级相等时也应当把栈顶弹出来因为从左到右的顺序要求先处理左侧的运算符右结合的运算符则相反遇到和栈顶优先级相等时不应该弹栈要继续压着等待右侧表达式先算完。2.3 括号天生就是“隔离区”括号在表达式里的角色也很像一对屏蔽标记左括号代表“从这里开始内部是一个独立的小世界”右括号代表“这个独立世界结束把内部积累的结果释放出来”。在转换算法中左括号的处理很直接——无条件压入运算符栈。因为括号内部可能有各种优先级的高低顺序我们要等右括号出现并开始清空栈时才把括号内的所有运算符按正确顺序弹出来。右括号的处理也很简单持续弹出栈顶运算符并输出到后缀列表直到遇到左括号为止。弹出的过程中左括号本身不要输出到后缀表达式里直接丢掉即可。这里有一个必须注意的边界如果栈已经弹出空了都还没有遇到左括号说明表达式里的右括号没有匹配的左括号这属于非法输入需要显式报错。括号的存在让运算符的优先级比较出现一个“暂停区”。在比较栈顶优先级时一旦发现栈顶是左括号就立刻停止弹出因为括号内的内容还没有处理完。这个细节写代码时非常容易漏。3. 实操过程与代码实现3.1 中缀转后缀函数逐段拆解这段代码是整个项目的核心我建议各位先自己写一遍再看下面的实现和拆解。贪图方便直接抄代码往往学不到踩坑的教训。def infix_to_postfix(expr: str) - list: precedence {: 1, -: 1, *: 2, /: 2, %: 2} assoc {: left, -: left, *: left, /: left, %: left} expr expr.replace( , ) output [] op_stack [] i 0 while i len(expr): ch expr[i] if ch.isdigit(): num ch while i 1 len(expr) and expr[i 1].isdigit(): i 1 num expr[i] output.append(num) elif ch (: op_stack.append(ch) elif ch ): while op_stack and op_stack[-1] ! (: output.append(op_stack.pop()) if not op_stack: raise ValueError(左括号缺失表达式不合法) op_stack.pop() elif ch in precedence: while (op_stack and op_stack[-1] ! ( and (precedence[op_stack[-1]] precedence[ch] or (precedence[op_stack[-1]] precedence[ch] and assoc[ch] left))): output.append(op_stack.pop()) op_stack.append(ch) else: raise ValueError(f无法识别的字符: {ch}) i 1 while op_stack: if op_stack[-1] (: raise ValueError(右括号缺失表达式不合法) output.append(op_stack.pop()) return output下面把几个关键部分拆开讲数字的多字符处理。如果只看单个字符123会被拆成1、2、3三个数字这显然不对。所以每遇到一个数字字符要准备一个内层循环持续向后读取直到读到一个非数字字符为止再把整个字符串作为一个操作数加入output。这里我用指针i在循环内部自增外层while里的i 1才能正确跳过已合并的字符。左括号无条件入栈。注意我的代码里左括号进入 op_stack 后并没有定义它的优先级因为它不参与排序。后续在比较栈顶运算符时条件里的op_stack[-1] ! (保证了左括号不会干扰优先级比较。右括号弹栈直到左括号。如果栈为空直接抛出ValueError。这个检查必须放在弹出循环之后因为弹栈循环的结束条件有两种可能正常遇到左括号或者栈空。区分这两种情况就靠这个if not op_stack。栈底残留运算符的清理。整个表达式扫描结束后运算符栈里可能还留着没来得及输出的运算符需要统一弹空。弹栈前要检查有没有未匹配的左括号有则说明括号没有闭合表达式非法。3.2 后缀表达式求值函数怎么写转换完成后求值阶段就轻松多了完全不需要关心优先级和括号只需要一个栈。def eval_postfix(tokens: list): stack [] for tok in tokens: if tok.isdigit(): stack.append(int(tok)) else: b stack.pop() a stack.pop() if tok : stack.append(a b) elif tok -: stack.append(a - b) elif tok *: stack.append(a * b) elif tok /: if b 0: raise ZeroDivisionError(除数为零) stack.append(a / b) elif tok %: if b 0: raise ZeroDivisionError(取模除数为零) stack.append(a % b) return stack[-1]这段代码里stack.pop()的顺序是一个经典考点。假设后缀表达式是1 2 -从左往右扫描先入栈1再入栈2遇到-时弹出的第一个数是2是减数第二次弹出的数才是1是被减数。所以必须用变量b保存先弹出的右操作数用变量a保存后弹出的左操作数否则1 2 -会被错算成2 - 1 1。这里我用的是 Python 的浮点除法因为表达式里如果出现1 / 5结果应当是 0.2 而不是 0。有些实训题目明确要求整数除法那就应该改成a // b但我建议先按浮点做最后再根据题目要求调整逻辑更稳。3.3 主流程串联与测试用例两个核心函数写好后主流程就只是读输入、做转换、做求值、打印结果。if __name__ __main__: expr 3 4 * 2 / (1 - 5) tokens infix_to_postfix(expr) print(后缀表达式:, .join(tokens)) print(运算结果:, eval_postfix(tokens))我用几个典型表达式做了测试结果如下输入表达式输出后缀计算结果1 2 * 31 2 3 * 7(1 2) * 31 2 3 *91 - 2 31 2 - 3 23 4 * 2 / (1 - 5)3 4 2 * 1 5 - / 3.51 2 * (3 - 4 * (5 6))1 2 3 4 5 6 * - * -77对照这些用例检查代码基本就能确认转换和求值都没有问题。尤其是1 - 2 3这个例子专门用来验证同级运算符的处理顺序如果优先级比较时把误写成结果会变成1 - (2 3) -4一下子就暴露错误。4. 常见问题与排查技巧实录4.1 优先级比较方向搞反同级运算顺序错乱这是我在实训里遇见的第一个 bug也是初学者最高频的错误。很多人会写这样的弹出条件while (op_stack and op_stack[-1] ! ( and precedence[op_stack[-1]] precedence[ch]):看着好像挺合理但问题出在相等的情况。以1 - 2 3为例扫描到的时候栈顶是-两者优先级相同。按照人的计算习惯1 - 2 3应该从左往右算也就是先算1 - 2再加上3结果等于 2。如果用作为弹出条件相等时不会触发弹栈而是直接压栈。表达式结束时栈里的运算是-后出、先出后缀变成1 2 3 -计算过程就变成1 - (2 3) -4结果完全错误。所以左结合运算符的弹出条件必须是栈顶优先级大于当前优先级或者栈顶优先级等于当前优先级且当前运算符为左结合。代码里我用了一个组合条件本质就是在说“栈顶不比我低就把它弹出来”。 注意如果你在题目中加入了幂运算^它的结合性是右结合相等时不能弹出而是让更靠右的幂先算否则2 ^ 3 ^ 2会算错。4.2 多位数没拼起来1234被拆成1 2 3 4字符串扫描最常见的坑就是忘记合并连续的多个数字字符。如果你只按单个字符处理123会被拆成三个 token后缀表达式变成1 2 3 4求值时它会一个一个压栈运算结果完全错乱。解决思路就是我在 3.1 中写过的遇到数字后不要急着前进用内层 while 循环把后续所有数字字符都读出来拼成一个完整的多位数。这个操作在词法分析里叫“最长匹配”或“贪心匹配”在表达式求值项目里虽然简单却至关重要。如果题目进一步要求支持小数这处逻辑还要扩展把小数点.也纳入数字字符的判断范围。但要注意一个小数表达式里只允许出现一个小数点如果出现两个点要主动报错别直接交给后面的求值阶段。4.3 括号不匹配和非法字符没拦住很多人写的求值器只处理“完全合法”的输入一旦遇到右括号多了、左括号少了、公式里混进了字母或中文符号程序要么直接崩溃要么给出毫无提示的IndexError: pop from empty list。我在实训中总结出的经验是报错要报得越早、越明确越好。在转换阶段就把能检测的非法情况全部拦住括号不匹配、无法识别的字符、运算符连续出现、表达式以运算符开头结尾等。最简单的做法是右括号弹栈时如果栈空或没有左括号直接抛出ValueError。表达式结束后如果 op_stack 里还残留左括号说明括号没闭合同样报错。遇到既不是数字也不是运算符、括号的字符立刻raise ValueError而不是悄悄跳过。把校验集中在转换阶段求值阶段就可以假设输入一定是合法的两个函数各司其职排查问题时思路清晰得多。4.4 负数与减法符号的辨析这是实训题目里最隐蔽的一个坑。输入-3 5时-在表达式开头它代表的不是减法而是一个负号。如果按普通运算符处理程序会试图在栈里弹出两个操作数来计算减法结果发现栈里只有一个操作数直接报了IndexError。处理负号的常见思路有两种。第一种是在转换阶段识别如果-出现的位置是“表达式开头”或者“前一个字符是运算符或左括号”就把它当成负号和后面的数字合并成一个 token比如-3。第二种更稳妥的思路是把-3转换成0 - 3的等价形式即在负号出现前补一个数字0。这个方法不需要改转换逻辑只需要在做预处理时替换文本。我当时用的就是第二种因为它最不易出错。比如-3 5预处理成0 - 3 5后面所有逻辑原样复用优先级、弹栈顺序都不用改。缺点是表达式会变长一点点但在课程实训场景下完全没问题。注意如果你在转换阶段直接把负号和数字拼成一个数后缀求值函数里就要能识别负数 token不能再用单纯的isdigit()判断否则会把-3当成运算符去处理。4.5 除零与取模零的边界防护最后一个小细节是除零。在求值阶段遇到/或%时如果弹出的右操作数b为 0程序会抛出ZeroDivisionError。这个错误其实在 Python 里自带但默认报错信息对用户不友好而且如果你的代码没有显式检查就继续使用a / b最终的报错可能是莫名其妙的float division by zero定位起来费劲。我在代码里加了一个显式判断并且抛出带中文说明的异常这样用户在评测时能立刻明白问题所在。如果你的题目要求“除零时输出特定提示”而不是抛异常那就更简单了改成打印提示并结束程序即可。5. 实训心得与扩展方向5.1 从“能跑”到“能过测试”的差距实训评测系统往往比你想象的更严格。它能跑通一个用例不算什么真正拿高分的写法至少要覆盖以下几类测试点多层括号嵌套比如1 (2 * (3 4))多位数和小数比如123 45.6负数参与运算比如-3 * (4 2)同级运算符连续出现比如8 / 2 * 4除零、括号不匹配等异常输入表达式里夹杂空格、Tab、全角符号等噪声字符。我见过很多同学写出来的代码能算12*3却在嵌套括号上崩掉或者在8 / 2 * 4上算成8 / (2 * 4) 1。这些问题不是算法思路不会而是细节和边界没扣到位。做实训项目时给自己列一个这样的测试清单对着清单一项项验证比盲目多写几遍代码有用得多。5.2 从这一题延伸出去的广阔天地表达式求值是很多高级主题的起跑线。如果你学有余力我强烈建议在完成基础功能后往下面几个方向扩展支持一元运算符。比如负号、逻辑非需要引入一元运算符的优先级和弹出规则。支持数学函数。比如sin(x)、max(1,2)本质上是把函数名当成一个运算符在遇到函数调用的括号时把参数传入。支持变量赋值。输入x 3; x 2 * 4需要在内存里维护一个符号表。尝试双栈直接求值。不转后缀只靠操作数栈和运算符栈边扫描边算体会与两步走方案的差异。尝试 AST 抽象语法树。把表达式解析成树形结构再对树进行后序遍历求值。这个过程其实和后缀表达式异曲同工但能帮你建立对“编译过程”更宏观的理解。在我个人看来这个实训项目最大的价值不在于那几十行代码本身而在于让你体会到一个相当通用的思维当问题里的“读取顺序”和“执行顺序”不一致时栈就天然地提供了缓冲和反转的空间。括号匹配、表达式求值、函数调用栈、撤销操作、深度优先搜索……这些场景背后都是同一个思想。把这个模板吃透你后面不管是学算法还是接触编译原理都会觉得很多东西其实是相互贯通的。当初那两个晚上踩过的坑、画过的状态图、打印过的调试信息后来都成了我理解更复杂系统时的底层直觉。实训的意义很多时候也正在这里。