1. 从一道25分题说起表达式转换到底在考什么表达式转换是数据结构与算法课程里非常经典的一类题目通常出现在栈与队列这一章。很多人第一次看到“中缀转后缀”或者“中缀转前缀”的时候会觉得这不就是个格式变换吗有什么难的。但真正动手写代码的时候才发现坑一个接一个运算符优先级怎么比较、括号怎么处理、多位数字怎么识别、负号和一元的正负号怎么区分、结合性怎么保证。这道25分的题考察的绝不仅仅是“会不会写栈”而是你对表达式结构本身的理解深度。先把这道题的核心需求说清楚。题目一般会给出一个中缀表达式要求你把它转换成后缀表达式也叫逆波兰表达式或者前缀表达式。中缀表达式就是我们平时写的3 4 * 2这种运算符在操作数中间。后缀表达式则是3 4 2 * 运算符在操作数后面。前缀表达式是 3 * 4 2运算符在前面。转换的意义在于后缀和前缀表达式不需要括号就能唯一确定运算顺序非常适合计算机用栈来求值。这道题适合谁看如果你正在学数据结构正在刷PTA或者类似平台的题目被表达式转换卡住了那这篇内容就是写给你的。如果你已经会了但每次写都要翻模板、调半天边界那也可以看看我是怎么把这件事拆成一套稳定流程的。我会从题目分析开始把核心原理讲透然后给出完整的代码实现最后重点讲那些真正容易踩坑的地方。这些坑我在实际写和帮别人调的过程中几乎每次都有人中招。提示表达式转换的题目描述通常很短但隐含条件很多。读题时一定要确认三件事——操作数是整数还是可能有多位、是否允许一元正负号、运算符集合具体有哪些。2. 中缀转后缀的底层逻辑栈到底在维护什么2.1 为什么后缀表达式不需要括号要理解转换算法先得理解后缀表达式为什么能去掉括号。中缀表达式里括号的作用是强制改变运算顺序。比如(3 4) * 2和3 4 * 2结果完全不同。但在后缀表达式里3 4 2 *和3 4 2 * 本身就编码了运算顺序因为运算符总是紧跟在它的两个操作数之后。你从左往右扫描遇到运算符就把它前面最近的两个操作数拿出来算算完的结果再放回去。这个过程天然就是按照表达式原本的嵌套结构来的不需要额外的括号标记。所以转换的本质就是把中缀表达式里“隐含在优先级和括号中的顺序信息”显式地重新排列成后缀形式。栈在这里的作用是暂存那些“还没轮到输出”的运算符。2.2 运算符优先级的比较规则转换算法的核心操作之一是比较当前运算符和栈顶运算符的优先级。规则是这样的当扫描到一个运算符时如果栈顶运算符的优先级大于等于当前运算符就把栈顶弹出并输出直到栈顶优先级小于当前运算符或者栈为空或者栈顶是左括号然后把当前运算符压栈。这里有个关键细节对于左结合的运算符加减乘除都是左结合当优先级相等时栈顶的要先弹出。因为左结合意味着从左往右算先出现的运算符应该先执行。比如3 - 4 5先算3 - 4再算 5所以遇到的时候栈顶的-要弹出来。优先级表可以这样定义运算符优先级结合性1左结合-1左结合*2左结合/2左结合(0栈内—)——左括号在栈内时优先级设为最低这样任何运算符遇到它都不会把它弹出来。右括号不压栈遇到右括号就一直弹栈直到遇到左括号然后把左括号弹出丢弃。2.3 扫描过程中的三类处理整个扫描过程可以归纳为三类处理遇到操作数直接输出。如果操作数可能有多位需要连续读取数字字符直到非数字。遇到左括号直接压栈。遇到右括号持续弹栈并输出直到弹出左括号为止左括号不输出。遇到运算符按照优先级规则弹栈然后压入当前运算符。扫描结束后如果栈不为空依次弹出并输出。这套流程看起来简单但真正写起来边界条件非常多。下面我先给出一个完整的代码实现然后再逐条分析那些容易出错的地方。3. 完整代码实现与逐段拆解3.1 基础版本只处理单位整数和四则运算先看一个最基础的版本假设操作数都是单个数字运算符只有加减乘除和括号。def infix_to_postfix(expr): precedence {: 1, -: 1, *: 2, /: 2} output [] stack [] for ch in expr: if ch.isdigit(): output.append(ch) elif ch (: stack.append(ch) elif ch ): while stack and stack[-1] ! (: output.append(stack.pop()) stack.pop() # 弹出左括号 elif ch in precedence: while (stack and stack[-1] ! ( and precedence[stack[-1]] precedence[ch]): output.append(stack.pop()) stack.append(ch) while stack: output.append(stack.pop()) return .join(output)这段代码逻辑清晰但有几个问题。第一它只能处理单个数字如果输入是12 34它会把1、2、3、4当成四个独立的操作数。第二它没有处理空格。第三它没有处理一元正负号。第四它假设输入一定是合法的。在实际题目中操作数往往是多位的整数输入可能包含空格也可能不包含。所以我们需要一个更健壮的版本。3.2 健壮版本支持多位整数和空格def infix_to_postfix_v2(expr): precedence {: 1, -: 1, *: 2, /: 2} output [] stack [] i 0 n len(expr) while i n: ch expr[i] if ch : i 1 continue if ch.isdigit(): num [] while i n and expr[i].isdigit(): num.append(expr[i]) i 1 output.append(.join(num)) continue if ch (: stack.append(ch) elif ch ): while stack and stack[-1] ! (: output.append(stack.pop()) if stack: stack.pop() elif ch in precedence: while (stack and stack[-1] ! ( and precedence[stack[-1]] precedence[ch]): output.append(stack.pop()) stack.append(ch) i 1 while stack: output.append(stack.pop()) return .join(output)这个版本用while循环代替for循环是为了在读取多位数字时能够控制索引。读取数字的时候一直读到非数字字符为止然后把整个数字作为一个整体输出。这样就解决了多位整数的问题。3.3 处理一元正负号的思路一元正负号是表达式转换里最容易出错的地方。比如-3 4这个-是一元负号不是减法运算符。再比如3 * (-2 5)括号里的-也是一元负号。怎么判断一个或-是一元还是二元看它前面的字符。如果它前面是操作数或者右括号那它就是二元运算符。如果它前面是运算符、左括号或者它出现在表达式开头那它就是一元运算符。一元正负号的处理方式有两种。一种是在转换之前先对表达式做预处理把一元负号替换成特殊标记比如#然后在转换时把#当成一个高优先级的一元运算符处理。另一种是在扫描过程中动态判断遇到一元负号时直接输出一个特殊符号或者特殊处理。在实际题目中如果题目没有明确说有一元正负号通常可以不用处理。但如果你想写一个通用的表达式转换器那就必须考虑。我个人的建议是先确认题目范围不要过度设计。如果题目只要求处理二元运算符那就不要引入一元逻辑否则容易把简单问题复杂化。4. 那些年我踩过的坑从WA到AC的完整排查链路4.1 坑一多位数字被拆散这是最常见的错误。很多人用for ch in expr遍历字符串然后判断ch.isdigit()直接把单个字符输出。如果输入是12 34输出就变成了1 2 3 4 完全错了。这个坑的本质是你把“字符”和“操作数”混为一谈了。在表达式里12是一个操作数不是两个操作数。解决方法就是用while循环连续读取数字字符直到遇到非数字为止。排查方法拿一个包含多位数字的测试用例比如100 200 * 3手动模拟你的代码看看输出里数字有没有被拆开。如果拆开了那就是这个问题。4.2 坑二右括号处理时忘记弹出左括号右括号的处理逻辑是持续弹栈并输出直到遇到左括号然后把左括号弹出但不输出。很多人写的时候弹到左括号就停了忘记把左括号也弹出来。这样左括号会留在栈里最后输出的时候多出一个(。这个坑的排查方法很简单用一个带括号的测试用例比如(3 4) * 2看看输出里有没有多余的括号。如果有那就是左括号没弹干净。4.3 坑三优先级比较时用了大于而不是大于等于前面说过对于左结合运算符优先级相等时栈顶的要先弹出。所以比较条件应该是precedence[stack[-1]] precedence[ch]而不是。如果你用了那么3 - 4 5会变成3 4 5 -而正确结果是3 4 - 5 。这个坑很隐蔽因为对于3 4 * 5这种优先级严格递增的表达式用和结果一样。只有遇到同级运算符连续出现时才会暴露。所以测试用例一定要包含3 - 4 5或者3 * 4 / 5这种同级连续的情况。4.4 坑四扫描结束后忘记弹出剩余运算符扫描结束后栈里可能还有运算符必须全部弹出并输出。很多人写着写着就忘了这一步导致输出不完整。比如3 4扫描完3、、4之后栈里还有如果不弹出输出就只有3 4。这个坑的排查方法用一个最简单的表达式3 4看看输出是不是3 4 。如果只有3 4那就是忘了最后弹栈。4.5 坑五空格处理不当有些题目的输入包含空格有些不包含。如果你的代码没有处理空格遇到空格可能会把它当成非法字符或者影响数字的连续读取。稳妥的做法是在扫描时跳过空格或者在读取数字时把空格也当作分隔符。但要注意空格的处理方式取决于题目要求。如果题目要求输出也带空格那输出时要用空格分隔。如果题目要求输出不带空格那就直接拼接。我见过有人输入处理了空格输出却忘了加空格结果格式错误。4.6 坑六一元负号被当成减号如果题目包含一元负号比如-3 4而你的代码把所有-都当成二元减号处理那就会出错。因为-3里的-前面没有操作数它不应该触发弹栈逻辑。判断一元负号的条件是-出现在表达式开头或者它前面是(或者它前面是另一个运算符。满足这些条件时它是一元负号应该直接输出或者特殊处理。这个坑的排查方法用-3 4和3 * (-2)这样的测试用例看看输出是否正确。5. 从后缀到前缀换个方向而已但细节不同5.1 中缀转前缀的两种思路中缀转前缀有两种常见思路。第一种是先把中缀转成后缀然后再把后缀转成前缀。第二种是直接从右往左扫描中缀表达式按照类似转后缀的规则处理最后把结果反转。第一种思路比较直观但需要两步转换代码量稍大。第二种思路更直接但扫描方向反过来之后括号的处理和优先级的比较规则都要相应调整。我个人的偏好是第二种因为一步到位而且能加深对转换本质的理解。但如果你只是应付题目第一种更不容易出错因为转后缀的逻辑你已经很熟了。5.2 从右往左扫描的规则调整从右往左扫描时遇到右括号就压栈遇到左括号就弹栈直到遇到右括号。运算符的优先级比较规则也要反过来当栈顶优先级大于当前运算符时弹出而不是大于等于。这是因为从右往左扫描时结合性的方向也反过来了。具体来说对于左结合运算符从右往左扫描时优先级相等不应该弹出栈顶因为右边的运算符应该先算。所以比较条件变成precedence[stack[-1]] precedence[ch]。这个细节非常容易搞错。如果你用转后缀的条件去写转前缀结果就会出错。测试用例可以用3 - 4 5正确的前缀应该是 - 3 4 5也就是(3 - 4) 5。5.3 代码实现与验证def infix_to_prefix(expr): precedence {: 1, -: 1, *: 2, /: 2} output [] stack [] i len(expr) - 1 while i 0: ch expr[i] if ch : i - 1 continue if ch.isdigit(): num [] while i 0 and expr[i].isdigit(): num.append(expr[i]) i - 1 output.append(.join(reversed(num))) continue if ch ): stack.append(ch) elif ch (: while stack and stack[-1] ! ): output.append(stack.pop()) if stack: stack.pop() elif ch in precedence: while (stack and stack[-1] ! ) and precedence[stack[-1]] precedence[ch]): output.append(stack.pop()) stack.append(ch) i - 1 while stack: output.append(stack.pop()) return .join(reversed(output))这段代码的关键点有三个一是从右往左扫描二是读取数字时要反向读取再反转三是最后输出要整体反转。验证的时候用3 4 * 2测试正确前缀是 3 * 4 2。用(3 4) * 2测试正确前缀是* 3 4 2。6. 测试用例设计与自检清单6.1 必须覆盖的测试场景写完代码之后不要随便跑一个用例就提交。下面这些场景必须全部覆盖场景输入示例期望后缀输出单运算符3 43 4 优先级递增3 4 * 23 4 2 * 优先级递减3 * 4 23 4 * 2 同级连续3 - 4 53 4 - 5 带括号(3 4) * 23 4 2 *嵌套括号((3 4) * 2)3 4 2 *多位数字12 34 * 512 34 5 * 混合复杂(12 34) * (5 - 6)12 34 5 6 - *把这些用例都跑一遍如果全部通过基本就没问题了。如果某个用例挂了对照前面的坑逐一排查。6.2 提交前的自检清单在提交之前问自己这几个问题多位数字有没有被拆散右括号处理时左括号有没有弹出优先级比较用的是还是扫描结束后有没有弹出剩余运算符空格有没有正确处理输出格式是否符合题目要求带空格还是不带空格如果题目有一元正负号有没有处理这七个问题基本上覆盖了表达式转换题目90%以上的错误来源。每次提交前过一遍能省下很多次WA。7. 一些实战中的经验与建议表达式转换这类题目看起来是考栈的操作实际上考的是你对边界条件的敏感度。我见过很多人算法思路完全正确但就是过不了原因全在细节上。比如输出格式多一个空格、少一个空格或者数字读取时索引越界。我的建议是写这类题目的时候先在纸上把算法流程画一遍特别是栈的变化过程。拿一个稍微复杂的表达式比如3 4 * 2 - (1 5)手动模拟每一步看看栈里有什么输出是什么。这个过程能帮你发现很多逻辑上的漏洞。另外不要一上来就写通用版本。先把最简单的版本写对只处理单位数字和四则运算跑通之后再逐步加功能。每加一个功能就加对应的测试用例。这样出问题的时候你能快速定位是哪一步引入的。还有一点关于一元正负号如果题目没有明确要求不要主动去处理。很多题目的测试数据里根本没有一元负号你加了反而可能引入新的bug。先看清楚题目范围再决定要不要扩展。最后说一个调试技巧。如果输出不对但你又看不出哪里错了可以在代码里加打印把每一步的栈状态和输出都打出来。对比手动模拟的结果很快就能找到偏差出现在哪一步。这个方法虽然笨但非常有效。注意不同平台对输出格式的要求可能不同。有的要求用空格分隔有的要求直接拼接。提交前一定要仔细看题目说明不要想当然。