中缀转后缀与表达式求值：栈的应用与实现详解

中缀表达式转后缀表达式再加上后缀表达式的求值这几乎是每个学《数据结构》的人都会撞上的一道坎。我当年第一次写这段代码的时候对着严蔚敏那本经典教材翻来覆去看了三遍纸上画了一堆栈的变化图结果上机一跑还是错——不是优先级判断漏了情况就是多位数字被拆成了单个字符。后来带学弟做实验报告、帮同事准备面试这套东西我前后实现过不下十遍用C、用Python、用Java都写过才慢慢把里面的坑一个个填平。这篇文章就是把这十来年攒下来的经验一次性讲清楚。核心关键词就几个中缀表达式、后缀表达式、数据结构、算法、栈。我会从设计思路讲到逐行实现把运算符优先级表、栈的变化过程、多位数字处理、括号匹配、负数和小数的边界情况全部拆开揉碎。不管你是正在赶数据结构实验报告的学生还是准备408考研复习的王道选手或者只是想把这块知识彻底搞明白的开发者看完都能自己动手写出一个能跑、能过测试、能讲清楚原理的版本。我默认你用任意一门语言都能看懂代码示例主要用C因为教材和考试大多用C关键逻辑会补充Python版本方便对照。整篇内容不依赖任何特定平台你复制到本地就能跑。1. 为什么这道题值得反复琢磨1.1 中缀和后缀到底差在哪我们平时写的3 4 * 2这种叫中缀表达式运算符夹在两个操作数中间符合人类阅读习惯。但计算机处理它很别扭因为运算符的优先级和括号会打乱从左到右的计算顺序。你想想3 4 * 2人一眼知道先算4 * 2可机器如果老老实实从左往右扫先遇到就想算3 4那就错了。后缀表达式也叫逆波兰表达式Reverse Polish Notation把运算符放到操作数后面3 4 * 2写成3 4 2 * 。它的好处是完全没有优先级和括号的困扰计算机只需要一个栈从左往右扫一遍就能算出结果。这也是为什么早期的计算器和很多编译器前端都采用这种表示法。所以整个任务被拆成两步第一步把人类友好的中缀转成机器友好的后缀第二步用栈把后缀算出来。两步的核心数据结构都是栈这也是这道题被放进《数据结构》栈章节的典型例题的原因。1.2 这道题到底在考什么表面上看是让你写两个函数实际上它在考你对栈这个数据结构的理解深度。转换过程考的是栈的延迟输出特性——遇到运算符不能马上输出得先压栈等后面有更高优先级的运算符或者括号结束时再弹出来。求值过程考的是栈的后进先出特性——遇到操作数压栈遇到运算符就弹出两个操作数计算再压回去。我见过太多人代码能跑但讲不清原理面试官一问为什么运算符要压栈而不是直接输出就卡壳。所以下面我不光给代码更要把每一步为什么这么做讲透。理解了原理你换任何语言、处理任何边界情况都不会慌。1.3 适合谁来读如果你是正在做数据结构实验的学生这篇能直接当你的实现参考和实验报告素材。如果你在准备408或者找工作的算法面试这里面的优先级表、边界处理、常见追问都是高频考点。如果你已经工作但想补基础这套栈的应用思路在解析配置、处理表达式、写简易计算器时都用得上。我尽量不假设你有很强的编程功底每个关键步骤都会解释意图。2. 整体设计思路与方案选型2.1 两个阶段的分工整个方案分成两个独立但衔接紧密的阶段。第一阶段是中缀转后缀输入是一个中缀表达式字符串输出是一个后缀表达式通常用列表或字符串保存。第二阶段是后缀求值输入是后缀表达式输出是一个数值结果。我强烈建议你把这两个阶段写成两个独立函数而不是揉在一起。原因有三一是便于单独测试转换对不对和求值对不对可以分开验证二是便于复用后缀表达式可以保存下来多次求值比如变量替换场景三是逻辑清晰出问题时能快速定位是转换错了还是求值错了。我早期图省事写成一个函数结果调试时根本分不清是哪一步出的错血的教训。2.2 为什么选栈而不是其他结构有人会问能不能用队列或者递归来做队列是先进先出处理不了运算符优先级的延迟需求。递归确实可以本质是表达式树的后序遍历但递归写法对初学者不友好而且栈溢出风险高。栈的后进先出恰好匹配运算符优先级的嵌套关系——优先级高的运算符后进栈也就先出栈天然符合先算优先级高的这个需求。用一个生活类比栈就像一摞盘子你只能从最上面拿。转换时运算符按优先级叠在栈里优先级高的压在优先级低的上面要输出时自然先拿上面的高优先级运算符。这个直觉建立起来代码就好写了。2.3 运算符优先级表的设计优先级表是整个转换算法的灵魂。我一般用两个维度来定义栈内优先级in-stack priority, ISP和栈外优先级incoming priority, ICP。为什么要分两个因为同一个运算符在栈内和栈外的待遇不一样。比如左括号(在栈外时优先级极高要赶紧压进去但在栈内时优先级极低要等右括号来才弹出。下面是我常用的优先级表这套数值在严蔚敏教材和多数408资料里都能对上运算符栈内优先级 ISP栈外优先级 ICP32-32*54/54(16)61规则是这样的当扫描到一个栈外运算符时如果它的栈外优先级大于栈顶运算符的栈内优先级就压栈否则弹出栈顶运算符输出再继续比较。左括号(栈外优先级最高6所以一遇到就压栈栈内优先级最低1所以任何运算符遇到它都不会弹出它直到右括号出现。右括号)栈外优先级最低1遇到它就要一直弹栈直到弹出左括号。注意这套数值不是唯一的你也可以用 -为1、* /为2、(为0 的简化版本只要保证相对大小关系正确即可。但用上面这套完整的表处理括号和边界时更不容易出错考试时也更好解释。2.4 多位数字与小数点的处理这是新手最容易翻车的地方。很多教材示例用的是单个数字比如34于是有人写代码时遇到数字就直接输出一个字符。但真实表达式里123 45这种多位数字太常见了你必须连续读取所有数字字符拼成一个完整的数再输出。我的做法是扫描到数字或小数点时进入一个内层循环一直读到非数字非小数点的字符为止把这段子串作为一个整体输出。这样123会被完整识别3.14也能正确处理。小数点要单独判断避免3.14.15这种非法输入被误读实际工程里我会加一个校验。2.5 负数与一元运算符的坑标准的中缀转后缀算法默认所有运算符都是二元的也就是-一定有两个操作数。但表达式-3 5里的-是一元负号只有一个操作数。这个情况如果不处理算法会出错。判断一元负号的规则是如果-出现在表达式开头或者出现在另一个运算符之后、左括号之后那它就是一元负号。处理方式有两种一是把-3整体当成一个负数操作数直接输出二是引入一个特殊的一元运算符比如用~表示负号给它最高优先级。我一般用第一种简单直接。这个细节考试不一定考但实际写计算器一定会遇到值得提前想清楚。3. 中缀转后缀的核心实现3.1 转换算法的完整流程先把整体流程用文字走一遍你脑子里有个全景图再看代码就不会迷路。算法维护一个运算符栈从左到右扫描中缀表达式的每个字符遇到操作数数字连续读取完整数字直接输出到后缀结果。遇到左括号(直接压栈。遇到右括号)不断弹出栈顶运算符并输出直到弹出左括号为止左括号弹出但不输出。遇到运算符比较它和栈顶运算符的优先级如果栈空或栈顶是左括号或当前运算符栈外优先级大于栈顶栈内优先级就压栈否则弹出栈顶输出重复比较直到满足压栈条件。扫描结束后把栈里剩余的运算符全部弹出输出。这个流程的关键在于第4步的重复比较很多人只比较一次就压栈导致3 * 4 2这种表达式转换错误。一定要用循环直到当前运算符能压进去为止。3.2 优先级判断的代码实现先定义优先级查询函数这是整个算法的基础设施// 返回栈内优先级非运算符返回 -1 int isp(char op) { switch (op) { case : case -: return 3; case *: case /: return 5; case (: return 1; case ): return 6; default: return -1; } } // 返回栈外优先级 int icp(char op) { switch (op) { case : case -: return 2; case *: case /: return 4; case (: return 6; case ): return 1; default: return -1; } }用switch而不是数组映射是因为运算符是字符switch可读性更好也方便你加新的运算符比如取模%、幂运算^。如果加^记得它的优先级要高于* /而且它是右结合的处理方式和普通二元运算符略有不同这个后面在常见问题里会讲。3.3 主转换函数的逐段拆解下面是转换函数的主体我用C写注释写得很细#include stdio.h #include stdlib.h #include string.h #include ctype.h #define MAX 1000 void infixToPostfix(const char *infix, char *postfix) { char stack[MAX]; // 运算符栈 int top -1; // 栈顶指针 int k 0; // 后缀结果的下标 int i 0; int len strlen(infix); while (i len) { char c infix[i]; // 跳过空格 if (c ) { i; continue; } // 情况1操作数连续读取多位数字和小数点 if (isdigit(c) || c .) { while (i len (isdigit(infix[i]) || infix[i] .)) { postfix[k] infix[i]; } postfix[k] ; // 用空格分隔操作数方便后续求值 continue; } // 情况2左括号直接压栈 if (c () { stack[top] c; i; continue; } // 情况3右括号弹栈直到左括号 if (c )) { while (top 0 stack[top] ! () { postfix[k] stack[top--]; postfix[k] ; } if (top 0) top--; // 弹出左括号但不输出 i; continue; } // 情况4运算符循环比较优先级 if (isp(c) ! -1) { while (top 0 isp(stack[top]) icp(c)) { postfix[k] stack[top--]; postfix[k] ; } stack[top] c; i; continue; } // 非法字符跳过或报错 i; } // 扫描结束弹出剩余运算符 while (top 0) { postfix[k] stack[top--]; postfix[k] ; } postfix[k] \0; }这段代码有几个设计决策值得说明。第一用空格分隔操作数这样后缀表达式里12和3不会粘成123求值时按空格切分就行比逐字符解析省事得多。第二多位数字用内层循环读取这是处理123这类数字的关键。第三右括号弹出左括号后不输出因为括号只是分组符号后缀表达式里不需要它。3.4 用具体例子跟踪栈的变化光看代码容易晕我们拿3 4 * 2 - (1 5)走一遍把每一步栈和输出的变化列出来。这个表达式够复杂包含了优先级和括号两种情况。步骤扫描字符操作栈内容底→顶后缀输出13输出空32压栈334输出3 44**的ICP4 的ISP3压栈 *3 452输出 *3 4 26--的ICP2 *的ISP5弹*再比23弹栈空压--3 4 2 * 7(压栈- (3 4 2 * 81输出- (3 4 2 * 19栈顶是(压栈- ( 3 4 2 * 1105输出- ( 3 4 2 * 1 511)弹到左括号弹输出弹(-3 4 2 * 1 5 12结束弹出-空3 4 2 * 1 5 -最终后缀表达式是3 4 2 * 1 5 -。你可以自己验算一下4*28381115611-65结果正确。这个跟踪表我建议你自己动手画一遍画完对算法的理解会上一个台阶。4. 后缀表达式求值的实现4.1 求值算法的核心逻辑后缀求值比转换简单得多因为没有了优先级和括号的干扰。算法维护一个操作数栈从左到右扫描后缀表达式遇到操作数转成数值压栈。遇到运算符弹出栈顶两个操作数注意顺序先弹出的是右操作数后弹出的是左操作数做运算把结果压回栈。扫描结束后栈里只剩一个数就是最终结果。这里最容易错的是操作数的顺序。栈是后进先出所以先弹出的是第二个操作数右操作数后弹出的才是第一个操作数左操作数。减法a - b和除法a / b对顺序敏感搞反了结果就错了。我见过太多人在这里栽跟头包括我自己第一次写的时候。4.2 操作数栈的代码实现// 后缀表达式求值假设操作数是整数 int evalPostfix(const char *postfix) { int stack[MAX]; int top -1; int i 0; int len strlen(postfix); while (i len) { char c postfix[i]; if (c ) { i; continue; } // 情况1操作数解析完整数字 if (isdigit(c)) { int num 0; while (i len isdigit(postfix[i])) { num num * 10 (postfix[i] - 0); i; } stack[top] num; continue; } // 情况2运算符弹出两个操作数计算 if (isp(c) ! -1) { int b stack[top--]; // 右操作数 int a stack[top--]; // 左操作数 int result 0; switch (c) { case : result a b; break; case -: result a - b; break; case *: result a * b; break; case /: result a / b; break; } stack[top] result; i; continue; } i; } return stack[top]; }注意num num * 10 (postfix[i] - 0)这行这是把字符数字转成整数的经典写法。postfix[i] - 0利用ASCII码把字符3转成整数3然后每次乘10加新位就能拼出多位数字。这个技巧在处理任何字符数字时都用得上。4.3 支持小数和浮点运算如果表达式里有小数上面的整数版本就不够用了。改成浮点版本核心变化是操作数栈用double解析数字时处理小数点double evalPostfixFloat(const char *postfix) { double stack[MAX]; int top -1; int i 0; int len strlen(postfix); while (i len) { char c postfix[i]; if (c ) { i; continue; } if (isdigit(c) || c .) { double num 0; // 整数部分 while (i len isdigit(postfix[i])) { num num * 10 (postfix[i] - 0); i; } // 小数部分 if (i len postfix[i] .) { i; double factor 0.1; while (i len isdigit(postfix[i])) { num (postfix[i] - 0) * factor; factor * 0.1; i; } } stack[top] num; continue; } if (isp(c) ! -1) { double b stack[top--]; double a stack[top--]; double result 0; switch (c) { case : result a b; break; case -: result a - b; break; case *: result a * b; break; case /: result a / b; break; } stack[top] result; i; continue; } i; } return stack[top]; }小数部分用factor逐位递减0.1、0.01、0.001...来累加逻辑清晰。不过要注意浮点精度问题0.1 0.2在计算机里不等于0.3这是IEEE 754标准的固有特性。如果对精度要求高得用定点数或者专门的十进制库这个在常见问题里会展开说。4.4 完整跑通一个例子把前面的转换和求值串起来测试3 4 * 2 - (1 5)int main() { char infix[] 3 4 * 2 - (1 5); char postfix[MAX]; infixToPostfix(infix, postfix); printf(后缀表达式: %s\n, postfix); int result evalPostfix(postfix); printf(计算结果: %d\n, result); return 0; }输出应该是后缀表达式: 3 4 2 * 1 5 - 计算结果: 5如果你跑出来是这个结果恭喜你核心逻辑通了。如果不对对照前面的栈变化表一步步排查八成是优先级比较或者操作数顺序的问题。5. 常见问题与排查技巧实录5.1 优先级比较写错导致的转换错误这是最高频的错误。典型症状是3 4 * 2被转成3 4 2 *错误而不是3 4 2 * 正确。根源在于比较运算符优先级时用了而不是或者只比较了一次没循环。记住规则当前运算符的栈外优先级icp要严格大于栈顶的栈内优先级isp才能压栈否则弹栈。用会导致相同优先级的运算符比如3 - 4 5里的不弹出前面的-破坏左结合性。3 - 4 5正确后缀是3 4 - 5 如果写成3 4 5 -结果就变成3 - (4 5) -6错了。5.2 多位数字被拆散的排查症状是12 3被转成1 2 3 求值时把1和2当成两个操作数。原因就是没写内层循环读取完整数字。排查方法很简单打印出后缀表达式看数字是不是完整的。修复就是加内层while循环把连续的数字字符一次性读完。提示用空格分隔操作数是个好习惯能避免12和3粘成123这种歧义。如果你不用空格求值时就得靠字符类型判断边界容易出错。5.3 括号不匹配的处理如果输入是(3 4少了右括号或者3 4)多了右括号算法会出问题。前者扫描结束时栈里还留着左括号后者遇到右括号时栈里找不到左括号。工程上必须加校验遇到右括号时如果栈空或栈顶不是左括号报括号不匹配。扫描结束后如果栈里还有左括号报括号不匹配。考试时如果题目保证输入合法可以省略校验但实际写计算器一定要加。我吃过亏用户输入个((34)程序直接崩了后来加了校验才稳。5.4 除零和非法运算后缀求值时遇到除法要先检查除数是否为零否则程序会崩溃或产生未定义行为。加一行判断case /: if (b 0) { printf(错误除数为零\n); return 0; // 或抛出异常 } result a / b; break;同理如果后缀表达式格式错误比如操作数不够弹栈时会越界也要加栈空判断。这些防御性代码在实验报告里可能不要求但实际项目里是必须的。5.5 常见问题速查表问题现象可能原因解决方法后缀表达式优先级错乱比较用了而非或没循环比较改用用while循环比较多位数字被拆散没写内层循环读数字连续读取数字字符拼成完整数减法/除法结果错误操作数弹出顺序反了先弹的是右操作数后弹的是左操作数括号相关崩溃没做括号匹配校验加栈空和左括号检查除零崩溃没检查除数除法前判断除数是否为零小数精度不对浮点误差用定点数或十进制库或设置误差容忍度5.6 几个容易被忽略的边界情况除了上面这些还有几个边界值得注意。空表达式要返回错误而不是崩溃。只有一个数字的表达式42转换后还是42求值返回42这个要能正确处理。连续运算符比如3 * -2这里的-是一元负号标准算法处理不了需要特殊判断。幂运算^的右结合性2 ^ 3 ^ 2应该是2 ^ (3 ^ 2) 512而不是(2 ^ 3) ^ 2 64处理时遇到^不能弹出栈里相同优先级的^比较条件要改成严格大于。这些边界情况考试不一定全考但你想把这道题真正吃透最好都实现一遍。我当年就是把这些都写了一遍才对栈的应用有了肌肉记忆。6. 从实验报告到面试考点的延伸6.1 实验报告怎么写才出彩如果你是在做数据结构实验报告光贴代码是拿不到高分的。我建议报告里包含这几块算法思路的文字描述用你自己的话讲清楚栈的作用、栈变化的跟踪表就像我前面那个表挑一个复杂表达式画出来、关键代码的注释说明每个判断的意图、测试用例和结果至少覆盖普通表达式、带括号、多位数字、小数这几种、复杂度分析时间O(n)空间O(n)n是表达式长度。复杂度分析很多人会漏。转换和求值都是线性扫描每个字符最多进栈出栈一次所以时间复杂度是O(n)。空间上栈的最大深度取决于表达式嵌套层数最坏情况也是O(n)。把这个讲清楚报告的专业度立刻上一个档次。6.2 面试里会怎么追问这道题在面试里经常作为栈的应用的引子面试官会顺着往下问。常见的追问有如果表达式里有变量怎么办答案是先做符号表替换或者求值时查表如果运算符有很多种怎么扩展用优先级表驱动加新运算符只改表递归和栈两种实现有什么区别递归本质是系统栈手动栈更可控不会栈溢出怎么处理函数调用比如sin(x)需要词法分析识别函数名然后按一元运算符处理。我面试别人的时候最喜欢问为什么后缀表达式不需要括号能答出因为运算符的位置已经隐含了运算顺序的人说明是真理解了。你也可以顺着这个思路把中缀、前缀、后缀三种表示法的关系理一遍面试时能讲出体系感。6.3 这套思路还能用在哪别以为这只是道练习题。配置文件解析里很多表达式求值比如条件判断、数值计算都用这套栈的思路。电子表格软件计算单元格公式底层就是中缀转后缀再求值。编译器前端把源代码表达式转成中间表示也是类似的流程。正则表达式引擎处理优先级和括号思路相通。我自己在做数据清洗时就写过一个简易表达式求值器让用户能输入price * 1.1 shipping这种公式底层用的就是这套中缀转后缀。理解了原理你就能根据实际需求灵活调整比如支持自定义函数、支持变量、支持字符串拼接等等。6.4 用Python快速验证你的思路如果你用C调试觉得麻烦可以用Python快速验证算法逻辑因为Python的列表天然就是栈写起来短平快def infix_to_postfix(expr): isp {:3, -:3, *:5, /:5, (:1, ):6} icp {:2, -:2, *:4, /:4, (:6, ):1} stack [] result [] i 0 while i len(expr): c expr[i] if c : i 1 continue if c.isdigit() or c .: num while i len(expr) and (expr[i].isdigit() or expr[i] .): num expr[i] i 1 result.append(num) continue if c (: stack.append(c) elif c ): while stack and stack[-1] ! (: result.append(stack.pop()) stack.pop() else: while stack and isp[stack[-1]] icp[c]: result.append(stack.pop()) stack.append(c) i 1 while stack: result.append(stack.pop()) return .join(result)Python版本逻辑和C完全一致但代码量少一半适合你快速验证思路。验证通过后再翻译成C能省很多调试时间。这是我常用的工作流先用Python把算法跑通确认逻辑无误再用C实现避免在指针和数组越界上浪费时间。6.5 一个我踩过的坑空格处理最后分享一个我早期踩的坑。有次我写的转换函数没处理输入里的空格用户输入3 4结果空格被当成非法字符虽然跳过了但影响了数字的连续读取判断。后来我统一在扫描开头跳过所有空格问题才解决。这个坑很小但很隐蔽因为不带空格的测试用例能过一带空格就出问题。提示如果你的输入可能包含制表符、换行符等空白字符用isspace()统一判断比只判断空格字符更稳妥。这套中缀转后缀加求值的实现我从学生时代写到工作每次重写都有新体会。最开始只求能跑后来追求边界完备再后来关注代码的可扩展性和可读性。如果你能把优先级表、栈变化过程、操作数顺序、边界处理这几块都吃透这道题就不再是考试题而是你工具箱里一个随时能用的技能。后续想扩展的话可以试试加上变量支持、函数调用、或者把它做成一个带图形界面的计算器都是很好的练手方向。