1. 从“12”到计算机的“语言”为什么我们需要三种表达式如果你刚开始学习数据结构与算法或者正在准备相关的面试那么“前缀表达式”、“中缀表达式”和“后缀表达式”这三个词大概率会让你感到一阵困惑。我们从小到大学的数学不都是像1 2这样写的吗为什么计算机世界里要搞出这么多“花里胡哨”的写法这背后其实是一个关于“人类友好”与“机器高效”之间巨大鸿沟的故事。我们人类习惯的1 2这种写法在计算机科学里被称为“中缀表达式”。它的特点是运算符,-,*,/写在两个操作数1和2的中间。这种写法非常直观符合我们的阅读和思维习惯。但是当表达式变得复杂比如(1 2) * 3 - 4 / 5时计算机要理解它就变得异常困难。难点在于“优先级”和“括号”的处理。计算机需要不断地“向前看”和“向后看”判断哪个运算符先计算括号从哪里开始到哪里结束这个过程对于顺序执行的计算机来说解析逻辑非常复杂效率低下。为了解决这个问题计算机科学家们发明了另外两种表达式表示法前缀表达式和后缀表达式。它们的核心思想是消除运算符的优先级和括号让表达式的计算顺序变得唯一且明确从而可以被计算机以一种非常简单、线性的方式通常借助栈这种数据结构高效地求值。简单来说中缀表达式给人看的直观但解析复杂。例如(1 2) * 3前缀表达式波兰表达式运算符在前操作数在后。例如* 1 2 3后缀表达式逆波兰表达式操作数在前运算符在后。例如1 2 3 *这篇文章我将带你彻底搞懂这三种表达式。我们不仅会弄清楚它们长什么样、怎么互相转换更重要的是我会结合栈这个核心数据结构手把手带你实现中缀转后缀的算法并完成后缀表达式的求值。这是编译原理、计算器设计、乃至很多表达式解析场景下的基础功理解了它你对“数据是如何被组织和处理”的认识会上一个台阶。2. 三种表达式的“样貌”与核心规则在深入技术细节之前我们必须先像认识新朋友一样搞清楚这三种表达式各自长什么样以及它们遵循的基本规则。2.1 中缀表达式我们最熟悉的“老朋友”中缀表达式就是我们日常书写数学表达式的方式。它的定义非常直接运算符位于两个操作数的中间。基本形式操作数1 运算符 操作数2例子A BA - B * C(A B) * (C - D)特点与挑战直观易读完全符合人类的思维和阅读习惯。需要定义优先级乘除*,/的优先级高于加减,-。需要括号来改变顺序当运算顺序不符合默认优先级时必须使用括号( )来显式指定。对计算机不友好计算机在解析时必须不断地“瞻前顾后”来判断下一个要执行的操作算法复杂度高。例如看到A - B * C它不能直接计算A - B必须看到后面的*和C才知道要先算B * C。2.2 前缀表达式运算符打头阵的“波兰式”前缀表达式也叫波兰表达式由波兰数学家扬·武卡谢维奇提出。它的核心规则是运算符位于其对应的两个操作数之前。基本形式运算符 操作数1 操作数2例子 A B等价于中缀的A B- A * B C等价于中缀的A - B * C注意这里* B C作为一个整体是-的第二个操作数* A B - C D等价于中缀的(A B) * (C - D)如何“阅读”前缀表达式前缀表达式的解析需要从右向左扫描但更通用的方法是递归地识别“运算符-操作数对”。对于- A * B C第一个符号是-这是一个运算符它需要两个操作数。接下来的A是第一个操作数。接下来的*又是一个运算符它也需要两个操作数因此* B C这个整体构成了-的第二个操作数。在* B C内部*的操作数是B和C。最大优点完全不需要括号来指定运算顺序运算符的位置本身就隐含了计算顺序。这使得它的求值算法可以非常简单地从右向左扫描并使用一个栈来存储操作数。2.3 后缀表达式操作数先行的“逆波兰式”后缀表达式也叫逆波兰表达式是前缀表达式的“镜像”。它的核心规则是运算符位于其对应的两个操作数之后。基本形式操作数1 操作数2 运算符例子A B 等价于中缀的A BA B C * -等价于中缀的A - B * C计算顺序先B C *得到结果R再A R -A B C D - *等价于中缀的(A B) * (C - D)如何“阅读”后缀表达式后缀表达式的解析是从左向右扫描这是它比前缀表达式更受欢迎的一个重要原因因为符合我们自然的阅读方向。算法极其优雅初始化一个空栈用于存放操作数。从左到右扫描表达式如果遇到操作数则将其压入栈中。如果遇到运算符则从栈中弹出两个操作数注意顺序先弹出的是右操作数后弹出的是左操作数用该运算符对它们进行运算然后将运算结果压回栈中。扫描结束后栈顶元素就是表达式的最终结果。为什么后缀表达式如此重要因为它完美地契合了“栈”这种后进先出数据结构的特性求值过程清晰、高效且无需处理优先级和括号。早期的一些计算器如HP计算器和许多编程语言的解释器内部都采用逆波兰表示法来处理表达式。注意在前缀和后缀表达式中运算符作用于其之后前缀或之前后缀最近的两个可用操作数。这个“最近”和“两个”的关系是理解其无歧义性的关键。3. 核心转换从中缀到后缀的“编译”过程理解了三种表达式的定义后最关键也最常考的一步来了如何将我们熟悉的中缀表达式转换为计算机更易处理的后缀表达式这个过程模拟了编译器前端的一部分工作。我们不能凭感觉移动运算符的位置需要一个系统化的算法。这个算法的核心依然是栈。我们需要一个栈来存放运算符和左括号。3.1 算法步骤与手动推演假设我们有中缀表达式A B * (C - D) / E我们的目标是得到后缀表达式。我们设定运算符的优先级*和/优先级为2和-优先级为1括号具有特殊作用。算法步骤如下初始化两个空结构一个用于输出后缀表达式的列表或字符串一个用于暂存运算符的栈。从左到右扫描中缀表达式的每个元素操作数、运算符、括号。对每个元素进行处理如果是操作数直接添加到输出列表。如果是左括号(将其压入运算符栈。如果是右括号)反复将栈顶的运算符弹出并添加到输出列表直到遇到左括号(。将左括号弹出丢弃不输出。如果是运算符记为op循环判断当栈不为空且栈顶运算符的优先级大于或等于op的优先级且栈顶元素不是左括号(时将栈顶运算符弹出并添加到输出列表。循环结束后将op压入栈中。当扫描完整个表达式后检查运算符栈。将栈中剩余的所有运算符依次弹出并添加到输出列表。输出列表连接起来就是最终的后缀表达式。让我们手动推演一遍A B * (C - D) / E扫描元素运算符栈 (栈底-栈顶)输出列表说明A空A操作数直接输出。A栈空入栈。BA B操作数直接输出。* *A B*优先级高于栈顶的直接入栈。( * (A B左括号直接入栈。C * (A B C操作数直接输出。- * ( -A B C-入栈。D * ( -A B C D操作数直接输出。) *A B C D -遇到右括号弹出栈顶至左括号弹出-输出弹出(丢弃。/ /A B C D - */与栈顶*优先级相等弹出*输出/优先级高于新栈顶/入栈。E /A B C D - * E操作数直接输出。结束空A B C D - * E / 扫描结束弹出栈中剩余所有运算符/,依次输出。最终后缀表达式A B C D - * E / 你可以用3.2节的后缀求值算法验证一下这个结果是否与原始中缀表达式等价。3.2 代码实现与关键细节理解了原理我们用代码来实现它。这里以支持 - * / ( )和整数操作数的简单版本为例。def infix_to_postfix(infix_expr): 将中缀表达式字符串转换为后缀表达式字符串。 假设输入表达式元素间有空格分隔如 A B * ( C - D ) / E # 定义优先级字典 precedence {: 1, -: 1, *: 2, /: 2} output [] # 输出列表 op_stack [] # 运算符栈 tokens infix_expr.split() # 按空格分割表达式 for token in tokens: if token.isalnum(): # 如果是操作数这里简单判断为字母或数字组合 output.append(token) elif token (: op_stack.append(token) elif token ): # 弹出直到遇到左括号 while op_stack and op_stack[-1] ! (: output.append(op_stack.pop()) op_stack.pop() # 弹出左括号丢弃 else: # token是运算符 - * / # 关键循环当栈顶运算符优先级 当前运算符且不是左括号时 while (op_stack and op_stack[-1] ! ( and precedence.get(op_stack[-1], 0) precedence.get(token, 0)): output.append(op_stack.pop()) op_stack.append(token) # 扫描结束弹出栈中所有剩余运算符 while op_stack: output.append(op_stack.pop()) return .join(output) # 测试 infix A B * ( C - D ) / E postfix infix_to_postfix(infix) print(f中缀表达式: {infix}) print(f后缀表达式: {postfix}) # 输出: A B C D - * E / 关键细节与踩坑点优先级比较中的“大于等于”在while循环判断时条件是precedence[栈顶] precedence[当前]。这意味着当遇到相同优先级的运算符时如和-*和/也要将栈顶的弹出。这保证了相同优先级的运算符按从左到右的顺序计算左结合性。如果只写对于A - B - C会得到错误的后缀表达式。括号的处理左括号(在入栈时具有最低的优先级实际上我们没给它赋值它只被右括号)匹配弹出。在遇到右括号前栈中的左括号像一个“屏障”阻止其下方的运算符被弹出。这是实现括号强制优先级的核心。操作数的判断示例中用了简单的token.isalnum()实际应用中可能需要更复杂的逻辑来识别负数、小数、函数名或变量名。空格分隔示例要求输入表达式有空格这是为了简化分词。一个更健壮的实现需要自己编写词法分析器来处理无空格的表达式如AB*(C-D)/E这会涉及更复杂的字符扫描和数字拼接。4. 后缀表达式的求值栈的经典舞台得到后缀表达式后求值就变得异常简单了。这正是后缀表达式设计的精妙之处求值算法只需要一个栈且严格从左到右扫描无需任何回溯或优先级判断。4.1 算法详解与示例我们以刚才得到的后缀表达式A B C D - * E / 为例假设A1, B2, C3, D4, E2。求值算法步骤初始化一个空栈用于存放操作数。从左到右扫描后缀表达式的每个元素。对每个元素如果是操作数将其转换为数值如果需要并压入栈中。如果是运算符从栈中弹出两个操作数。注意顺序先弹出的是右操作数right后弹出的是左操作数left。对于减法和除法顺序至关重要。执行运算left op right。将运算结果压回栈中。扫描结束后栈中应只剩下一个元素即为表达式的最终结果。手动求值1 2 3 4 - * 2 / (其中A1, B2, C3, D4, E2)扫描元素操作数栈 (栈底-栈顶)动作说明11操作数入栈。21 2操作数入栈。31 2 3操作数入栈。41 2 3 4操作数入栈。-1 2 -1弹出4(右),3(左)计算3 - 4 -1结果入栈。*1 -2弹出-1(右),2(左)计算2 * (-1) -2结果入栈。21 -2 2操作数入栈。/1 -1弹出2(右),-2(左)计算-2 / 2 -1结果入栈。0弹出-1(右),1(左)计算1 (-1) 0结果入栈。最终结果0。验证一下原中缀表达式1 2 * (3 - 4) / 2 1 2 * (-1) / 2 1 (-2) / 2 1 (-1) 0结果正确。4.2 代码实现与错误处理def evaluate_postfix(postfix_expr, var_dictNone): 计算后缀表达式的值。 postfix_expr: 空格分隔的后缀表达式字符串如 1 2 3 4 - * 2 / var_dict: 可选变量名到值的映射字典如 {A: 1, B: 2} stack [] tokens postfix_expr.split() for token in tokens: if token.replace(., , 1).isdigit() or (token[0] - and token[1:].replace(., , 1).isdigit()): # 处理整数、小数、负数 stack.append(float(token) if . in token else int(token)) elif var_dict and token in var_dict: # 如果是变量从字典中取值 stack.append(var_dict[token]) else: # 是运算符 if len(stack) 2: raise ValueError(f无效的后缀表达式运算符 {token} 缺少足够的操作数) right stack.pop() left stack.pop() if token : result left right elif token -: result left - right elif token *: result left * right elif token /: if right 0: raise ZeroDivisionError(除零错误) result left / right else: raise ValueError(f不支持的运算符: {token}) stack.append(result) if len(stack) ! 1: raise ValueError(无效的后缀表达式表达式不完整或格式错误) return stack[0] # 测试1直接计算数值表达式 postfix_num 1 2 3 4 - * 2 / print(f后缀表达式 {postfix_num} 的结果是: {evaluate_postfix(postfix_num)}) # 输出: 0.0 # 测试2计算含变量的表达式 postfix_var A B C D - * E / var_values {A: 10, B: 20, C: 5, D: 2, E: 2} print(f后缀表达式 {postfix_var} (A10, B20, C5, D2, E2) 的结果是: {evaluate_postfix(postfix_var, var_values)}) # 计算: 10 20 * (5-2) / 2 10 20*3/2 1030 40 # 输出: 40.0关键细节与踩坑点操作数弹出顺序这是最容易出错的地方。栈是后进先出所以当遇到运算符时先弹出的是右操作数后弹出的是左操作数。对于加法和乘法顺序不影响结果但对于减法和除法left - right和left / right才是正确的。错误处理一个健壮的求值器必须处理错误情况操作数不足当遇到运算符时栈中元素少于2个。除零错误在除法运算中右操作数为0。无效运算符遇到了未定义的运算符。表达式不完整扫描结束后栈中元素数量不为1可能多也可能少。数据类型示例中统一使用了float来容纳除法和可能的小数结果。在实际应用中可能需要根据需求区分整数和浮点数运算。变量替换如果后缀表达式包含变量如A, B, C需要在求值前提供一个变量名到具体数值的映射字典。5. 前缀表达式的求值与转换虽然前缀表达式不如后缀表达式常用但理解其求值和与中缀的转换也是完整的知识闭环。5.1 前缀表达式求值前缀表达式求值是从右向左扫描同样使用一个栈。但与后缀求值栈存操作数不同前缀求值栈通常用来存中间结果不过更直观的方法是递归求值或使用操作数栈并从右向左扫描。从右向左扫描的算法初始化一个空栈操作数栈。从右向左扫描前缀表达式。对每个元素如果是操作数压入栈中。如果是运算符从栈中弹出两个操作数注意顺序此时先弹出的是左操作数后弹出的是右操作数因为扫描方向反了执行运算左操作数 op 右操作数将结果压回栈中。扫描结束后栈顶元素即为结果。示例前缀表达式* 1 2 3等价于中缀(12)*3从右向左扫描3(入栈) -2(入栈) -1(入栈) -(弹出1和2计算123入栈) -*(弹出3和3计算3*39入栈)。结果9。5.2 中缀转前缀算法中缀转前缀的算法思路与转后缀类似但更复杂一些通常有两种方法方法一推荐先将中缀表达式反转然后按照类似中缀转后缀的算法处理但需要调整括号和优先级比较的方向得到的结果再反转回来。这是因为前缀表达式是“运算符-操作数-操作数”的结构从右向左处理更自然。方法二递归找到中缀表达式中最后计算的运算符即优先级最低且最靠右的运算符括号外以此运算符为根递归地将其左右两部分转换为前缀表达式。由于前缀表达式在实际应用中较少且转换算法相对繁琐这里不展开详细代码实现。理解其与后缀表达式的对称性以及“从右向左”的特性更为重要。6. 实际应用场景与扩展思考学完了原理和算法这些知识到底用在哪里呢绝不仅仅是应付考试。计算器与表达式求值这是最直接的应用。许多编程语言如Forth、PostScript和早期硬件计算器直接使用逆波兰表示法。现代编程语言的解释器和编译器在解析表达式时内部也会先将中缀表达式转换为一种类似后缀的中间表示如抽象语法树的三地址码再进行求值或优化。编译原理中缀转后缀的算法是编译器“语法分析”阶段的一个简化模型。编译器需要将源代码中的复杂表达式解析成计算机能顺序执行的指令序列这个过程中就需要处理运算符优先级、结合性和括号。调度场算法我们实现的中缀转后缀算法其核心思想就是著名的“调度场算法”。它像铁路调度场一样将操作数车厢直接输出到正确的轨道将运算符车头暂时存放在栈侧线上等待合适的时机再输出。函数式编程前缀表达式( 1 2)这种形式与Lisp、Scheme等函数式编程语言的语法非常相似。在这些语言中函数调用本身就是前缀形式的。解决特定问题有些问题天然适合用栈来处理表达式。例如LeetCode上就有多道关于基本计算器实现加减乘除和括号的题目其核心解决方案就是中缀转后缀再求值或者用双栈直接模拟。扩展思考如何处理一元运算符例如负号-A或阶乘A!。这需要在词法分析时区分一元和二元减号并在转换和求值算法中为它们定义不同的逻辑。如何支持函数调用例如max(A, BC)。函数名可以视为一个特殊的运算符其“操作数”是括号内的参数列表本身可能又是一个表达式这需要更复杂的语法树来构建。如何支持赋值运算符例如A B C。这涉及到表达式求值和变量存储两个不同的阶段。我自己在第一次实现这个算法时曾在优先级判断的“大于等于”上栽过跟头写成了“大于”导致一连串的同级运算符如1-2-3计算顺序错误。调试了很久才发现是结合性没处理好。另一个坑是在处理多位数和负数时简单的按字符分割会出问题“-123”会被分成‘-‘‘1’‘2’‘3’必须实现一个完整的词法分析器来正确识别数字和运算符。这些细节恰恰是区分“懂了原理”和“能写出健壮代码”的关键。