中缀转后缀与表达式求值：栈的经典应用与工程实践

中缀表达式转后缀表达式再算后缀表达式的值这个题目在数据结构课程里出现的频率高得离谱。不管是期末考、考研408还是面试手撕代码栈这一章绕来绕去最后大概率都要落到这道题上。我当年第一次学的时候也觉得不就是个转换吗结果自己动手写的时候才发现坑一个接一个运算符优先级怎么比、括号什么时候弹、多位数字怎么处理、负数怎么办、除零怎么防。这篇文章就把这套东西从头到尾捋一遍把我在实际编码和教学里踩过的坑都摊开讲清楚。1. 为什么这道题值得反复练1.1 它到底在练什么能力很多人把中缀转后缀当成一个孤立的算法题来背其实它练的是三件事的综合运用。第一是对栈这种后进先出结构的直觉你得理解为什么运算符要暂存在栈里而不是立刻输出。第二是对优先级和结合性的精确建模这是编译原理里表达式解析的雏形。第三是把一个复杂问题拆成两个独立子问题的工程思维转换和求值分开做各自职责单一。我见过不少同学转换写对了求值的时候又把中缀的逻辑混进去结果代码一团乱。根子就在于没想清楚这两个阶段的边界。转换阶段的输出是一个不含括号、运算符顺序已经确定的序列求值阶段只需要从左到右扫描这个序列遇到数字压栈遇到运算符弹两个算一下再压回去。两个阶段通过一个序列解耦这就是分治思想最朴素的体现。1.2 实际场景里它出现在哪别以为这东西只存在于试卷上。编译器前端把源代码里的算术表达式转成中间表示用的就是类似后缀的思想。计算器类应用、电子表格的公式引擎、数据库的表达式求值模块底层都跑着这套逻辑。甚至你写一个简单的规则引擎让用户配置a b * 2 10这样的条件解析和求值也离不开它。所以练这道题不是为了应付考试是在建立一种把人类习惯的书写形式翻译成机器易处理形式的通用能力。理解了这一层后面学语法分析、抽象语法树会觉得顺理成章。1.3 适合什么基础的人看只要你会一门编程语言的基本语法知道数组和循环怎么写就能跟上。栈这个结构如果还不熟文章里会顺带讲清楚它的核心操作。我会用 C 语言作为主要示例因为数据结构教材普遍用 C而且指针和数组的操作能让你看清内存层面的细节。如果你用 Python 或 Java逻辑完全一样只是语法换一下。2. 核心概念先把地基打牢2.1 中缀、后缀、前缀到底差在哪中缀表达式就是我们日常写的3 4 * 2运算符夹在两个操作数中间。人看起来舒服但机器处理起来麻烦因为要考虑优先级和括号不能简单地从左往右算。后缀表达式又叫逆波兰表达式把运算符放在操作数后面3 4 * 2写成3 4 2 * 。它的好处是完全没有歧义不需要括号从左到右扫描一遍就能算出结果。前缀表达式则是运算符在前 3 * 4 2性质类似但扫描方向相反。三种形式表达的是同一个计算区别只是运算符的位置。转换的本质就是根据优先级规则重新排列运算符的顺序。2.2 栈在其中的角色栈的核心特性是后进先出。在中缀转后缀的过程中栈用来暂存还没轮到输出的运算符。为什么用栈而不是队列因为运算符的输出顺序取决于它后面出现的运算符优先级。比如3 4 * 2读到的时候不能立刻输出因为后面可能有更高优先级的*得先让*参与运算。这个等一等看看后面的需求正好对应栈的暂存能力。求值阶段栈的作用更直接遇到数字压进去遇到运算符就弹出最近的两个数字做运算。因为后缀表达式的运算符顺序已经保证了操作数就在栈顶附近弹出来就能用。2.3 优先级与结合性的规则表这是整个算法的规则基础必须记牢。我整理成一张表方便对照。运算符优先级结合性说明(最高入栈时不适用左括号入栈后优先级视为最低直到遇到右括号)不适用不适用触发弹出直到左括号*/2左结合同级从左往右算-1左结合同级从左往右算左结合的意思是a - b - c等于(a - b) - c不是a - (b - c)。这个规则在转换时体现为当栈顶运算符优先级大于等于当前运算符时就要弹出栈顶。注意是大于等于等号不能漏否则左结合就变成了右结合结果会错。注意左括号入栈后它的优先级要特殊处理。在比较时左括号的优先级设为最低这样任何运算符遇到它都不会把它弹出来直到遇到右括号才主动弹出。3. 中缀转后缀的完整实现3.1 算法流程逐步拆解整个转换过程就是从左到右扫描中缀表达式对每个字符分情况处理。我用一个具体的例子贯穿3 4 * 2 - ( 1 6 ) / 3。扫描规则是这样的遇到数字直接输出到结果序列。遇到左括号压入栈。遇到右括号不断弹出栈顶运算符并输出直到遇到左括号然后把左括号弹出丢弃。遇到运算符先比较它和栈顶运算符的优先级。如果栈顶优先级大于等于当前运算符就弹出栈顶并输出重复这个过程直到栈空或栈顶优先级更低或栈顶是左括号然后把当前运算符压栈。扫描结束后把栈里剩余的运算符依次弹出输出。这个规则里最容易出错的是第4步的循环条件。很多人只比较一次就压栈导致3 - 4 2这种同级的情况处理错误。必须是循环把所有该弹的都弹干净。3.2 手把手走一遍转换过程拿3 4 * 2 - ( 1 6 ) / 3来走一遍每一步都记录栈和输出的状态。步骤读入操作栈内容底到顶输出序列13数字直接输出空32栈空压栈334数字直接输出3 44*栈顶优先级1*优先级2不弹压栈 *3 452数字直接输出 *3 4 26-栈顶优先级2 -优先级1弹出栈顶优先级1 -优先级1弹出栈空压--3 4 2 * 7(左括号压栈- (3 4 2 * 81数字直接输出- (3 4 2 * 19栈顶是左括号不弹压栈- ( 3 4 2 * 1106数字直接输出- ( 3 4 2 * 1 611)弹出输出遇到左括号弹出丢弃-3 4 2 * 1 6 12/栈顶-优先级1 /优先级2不弹压栈- /3 4 2 * 1 6 133数字直接输出- /3 4 2 * 1 6 314结束弹出/弹出-空3 4 2 * 1 6 3 / -最终后缀表达式是3 4 2 * 1 6 3 / -。你可以自己验算一下原式中缀的结果是3 8 - 7 / 3注意这里 7/3 在整数运算下是 2所以结果是11 - 2 9。后缀算出来也应该是 9。3.3 多位数字和负数的处理上面的例子都是个位数实际输入里肯定有多位数比如123。处理办法是遇到数字字符时不要立刻输出而是继续往后读把连续的数字字符拼成一个完整的数再输出。同时要在数字之间加分隔符否则12和3拼在一起变成123就分不清了。我通常用空格作为分隔符输出序列里每个数字和运算符之间都用空格隔开。这样求值阶段按空格切分就很方便。负数是个更隐蔽的坑。-3 5里的负号是单目运算符不是减法。判断方法如果负号出现在表达式开头或者出现在另一个运算符之后、左括号之后那它就是负号。处理方式可以是在转换前把-3整体当成一个数字处理或者在求值阶段特殊判断。我倾向于在转换阶段就把单目负号识别出来给它一个特殊标记求值时单独处理。3.4 C语言核心代码实现下面是转换函数的核心代码用数组模拟栈假设输入是已经用空格分隔好的 token 序列。#include stdio.h #include string.h #include stdlib.h #include ctype.h #define MAX 1000 // 判断是否为运算符 int isOperator(char *token) { return (strcmp(token, ) 0 || strcmp(token, -) 0 || strcmp(token, *) 0 || strcmp(token, /) 0); } // 获取优先级 int getPriority(char *op) { if (strcmp(op, *) 0 || strcmp(op, /) 0) return 2; if (strcmp(op, ) 0 || strcmp(op, -) 0) return 1; return 0; } // 中缀转后缀tokens是输入token数组n是数量output存结果 void infixToPostfix(char tokens[][20], int n, char output[][20], int *outLen) { char stack[MAX][20]; int top -1; *outLen 0; for (int i 0; i n; i) { char *tok tokens[i]; if (strcmp(tok, () 0) { // 左括号直接压栈 strcpy(stack[top], tok); } else if (strcmp(tok, )) 0) { // 右括号弹出直到左括号 while (top 0 strcmp(stack[top], () ! 0) { strcpy(output[(*outLen)], stack[top--]); } if (top 0) top--; // 弹出左括号丢弃 } else if (isOperator(tok)) { // 运算符比较优先级 while (top 0 strcmp(stack[top], () ! 0 getPriority(stack[top]) getPriority(tok)) { strcpy(output[(*outLen)], stack[top--]); } strcpy(stack[top], tok); } else { // 数字直接输出 strcpy(output[(*outLen)], tok); } } // 弹出剩余运算符 while (top 0) { strcpy(output[(*outLen)], stack[top--]); } }这段代码的关键点在于while循环里的三个条件栈非空、栈顶不是左括号、栈顶优先级大于等于当前运算符。三个条件缺一不可。我见过有人漏掉左括号判断结果括号内的运算符被错误弹出。实操心得用数组模拟栈的时候top初始化为 -1 比 0 更不容易出错因为top -1就代表空栈判断逻辑统一。如果用 0 表示空栈压栈和弹栈的边界条件容易写混。4. 后缀表达式求值的实现4.1 求值算法的核心逻辑后缀求值比转换简单得多因为不需要考虑优先级和括号。从左到右扫描后缀序列遇到数字就压栈遇到运算符就弹出两个操作数先弹出的是右操作数后弹出的是左操作数做完运算把结果压回去。扫描结束后栈里剩下的唯一一个数就是结果。这里有个顺序问题必须强调对于减法和除法先弹出的是右操作数。比如5 3 -先弹出 3再弹出 5计算5 - 3 2。如果搞反了变成3 - 5结果就错了。这是初学者最容易犯的错误没有之一。4.2 用刚才的例子验证后缀序列3 4 2 * 1 6 3 / -逐步走一遍。步骤读入操作栈内容底到顶13压栈324压栈3 432压栈3 4 24*弹2和4算4*28压栈3 85弹8和3算3811压栈1161压栈11 176压栈11 1 68弹6和1算167压栈11 793压栈11 7 310/弹3和7算7/32压栈11 211-弹2和11算11-29压栈9结果是 9和中缀直接算一致。注意第10步整数除法 7/3 得 2这是 C 语言的默认行为。如果你需要浮点结果得用 double 类型。4.3 求值代码实现// 后缀表达式求值假设都是整数运算 int evalPostfix(char output[][20], int outLen) { int stack[MAX]; int top -1; for (int i 0; i outLen; i) { char *tok output[i]; if (isOperator(tok)) { // 注意弹出顺序先右后左 int right stack[top--]; int left stack[top--]; int result 0; if (strcmp(tok, ) 0) result left right; else if (strcmp(tok, -) 0) result left - right; else if (strcmp(tok, *) 0) result left * right; else if (strcmp(tok, /) 0) { if (right 0) { printf(错误除数为零\n); return -1; } result left / right; } stack[top] result; } else { // 数字转整数压栈 stack[top] atoi(tok); } } return stack[top]; }除零判断必须加否则程序直接崩溃。这是工程代码和试卷代码的区别试卷上不写没关系实际项目里不写就是事故。4.4 浮点数和精度问题如果表达式里涉及小数把栈的类型从int换成doubleatoi换成atof。但浮点数比较相等是个坑比如判断结果是否为零不能直接用 0要用一个极小的阈值比如1e-9。这个细节在表达式求值里不常遇到但如果你的计算器要支持科学计算就得考虑。5. 常见问题与排查技巧实录5.1 转换结果不对怎么排查转换出错基本逃不出这几个原因。第一是优先级比较用了大于而不是大于等于导致同级运算符没有弹出左结合变成了右结合。第二是右括号处理时忘了弹出左括号导致左括号残留在栈里最后被输出。第三是扫描结束后忘了弹出栈里剩余的运算符。排查方法很简单拿一个包含同级运算符的表达式比如a - b c手动走一遍看输出是不是a b - c 。如果是a b c -就说明同级没弹。再拿一个带括号的( a b ) * c正确输出是a b c *如果输出里出现了括号就说明括号处理有问题。5.2 求值结果不对怎么排查求值出错最常见的就是减法和除法的操作数顺序搞反。排查时打印每次弹栈的值看左右操作数对不对。另一个常见问题是数字解析多位数被拆成了单个数字或者数字和运算符粘连。检查你的 token 切分逻辑确保每个 token 是完整的。还有一种隐蔽的错误栈溢出或栈下溢。表达式不合法时比如3 求值阶段会遇到运算符但栈里只有一个数弹两次就下溢了。工程代码里要加栈大小检查发现异常及时报错而不是让程序崩溃。5.3 常见问题速查表问题现象可能原因解决方法同级运算符顺序错误优先级比较用了而非改为大于等于输出里出现括号右括号处理时没弹出左括号遇到右括号后弹出并丢弃左括号最后结果少了运算符扫描结束后没弹栈循环弹出栈中剩余运算符减法结果反了弹栈顺序错误先弹右操作数后弹左操作数多位数被拆分逐字符处理而非按 token按空格切分或连续读取数字除零崩溃没做除零判断除法前检查除数是否为零负数被当成减号没识别单目负号根据上下文判断负号位置5.4 几个我踩过的坑第一个坑是输入格式。我一开始写的代码假设输入没有空格结果遇到123这种就懵了因为12是两个字符。后来改成先做词法分析把输入切成 token 数组后面所有逻辑都基于 token 操作清爽很多。这个思路其实就是编译原理里词法分析和语法分析分离的雏形。第二个坑是括号嵌套。( ( a b ) * c )这种多层嵌套右括号处理时只要遇到第一个左括号就停不要继续弹。因为内层括号处理完后外层括号还在栈里等着。这个逻辑用 while 循环加左括号判断就能正确处理。第三个坑是表达式合法性校验。实际使用中用户可能输入3 * 4这种非法表达式如果不做校验程序行为不可预测。我的做法是在转换阶段检查运算符出现时栈里是否有足够的操作数括号是否匹配。这些校验加上去代码健壮性提升一个档次。提示如果你是在准备考试重点放在算法逻辑和手算过程上。如果是在做实际项目词法分析、错误处理、边界检查这些工程细节比算法本身更花时间但决定了代码能不能用。6. 从会写到写好还差什么把中缀转后缀和求值写出来只是第一步。真正拉开差距的是对边界情况的处理和对代码结构的组织。我现在的习惯是把整个功能拆成三个模块词法分析负责把输入字符串切成 token转换模块负责中缀转后缀求值模块负责计算。每个模块单独测试出了问题定位很快。另外这套逻辑稍加改造就能支持更多运算符比如取模%、幂运算^。幂运算是右结合的2 ^ 3 ^ 2等于2 ^ (3 ^ 2)而不是(2 ^ 3) ^ 2所以优先级比较的条件要针对右结合运算符特殊处理。这个扩展练手很有价值能让你真正理解结合性对算法的影响。如果你用 Python 写可以用列表当栈append和pop就是压栈弹栈代码量能少一半。但底层逻辑一模一样建议先用 C 写一遍理解内存操作再用 Python 写一遍体会语言抽象带来的便利。两种都写过之后你对栈的理解会扎实很多。