扫码获取 VIP 码
添加管理员微信获取 VIP 码
在计算机科学尤其是编译原理与数据结构课程中，表达式的表示方法是一个绕不开的基础概念。日常书写的算术表达式，例如 a 加上 b 乘以 c 写作 a + b * c，运算符总是位于两个操作数之间，这种记法称为中缀表达式。中缀表达式符合人类长期养成的书写习惯，但它有一个致命的问题：表达式中必须依赖括号和运算符优先级规则才能准确表达运算顺序。计算机在扫描和处理这种表达式时，需要额外维护优先级和结合性的判断逻辑，处理起来并不直观。为了消除这种歧义，波兰逻辑学家扬·武卡谢维奇于二十世纪二十年代提出了一种将运算符置于操作数之前的记法，后来被称为前缀表达式或波兰式；而将运算符置于操作数之后的记法则称为后缀表达式，也就是逆波兰式。
逆波兰表达式的核心定义可以这样表述：在一个表达式中，如果每个运算符都紧跟在它所作用的操作数之后，并且运算符的作用对象是它左边紧邻的最近两个尚未参与运算的操作数，那么这种表达式就是后缀表达式。例如，中缀表达式 a + b 对应的后缀形式是 a b +，中缀表达式 a + b c 对应的后缀形式是 a b c +。从形式上看，后缀表达式不再需要任何括号，因为运算符出现的先后顺序已经隐含了运算的先后顺序。这种把运算顺序显式编码在运算符位置上的特性，正是逆波兰表达式的本质价值所在。
与前缀表达式相比，后缀表达式的差异仅仅在于运算符的位置。前缀表达式要求运算符写在两个操作数之前，例如中缀表达式 a + b 对应的前缀形式是 + a b，a + b c 对应的前缀形式是 + a b c。两种记法都消除了括号，都能被计算机从左到右或从右到左一遍扫描完成求值。但后缀表达式有一个工程上的优势：它天然符合栈的从左到右处理方式，求值过程与人类从左到右阅读的习惯一致，因此在编译器生成中间代码和各类表达式求值引擎中被广泛采用。相比之下，前缀表达式通常需要从右到左扫描，或者借助递归下降的方式处理，工程实现上稍显繁琐。
需要特别强调的是，中缀、前缀、后缀三种记法在语义上是完全等价的，它们描述的是同一棵表达式树。任何一棵表达式树，其叶子节点是操作数，内部节点是运算符，对这颗树分别进行中序遍历、前序遍历和后序遍历，就依次得到中缀表达式、前缀表达式和后缀表达式。这个对应关系是理解三者转换的钥匙：所谓中缀转后缀，本质上就是把表达式树的中序遍历结果改写为后序遍历结果，而栈在这个改写过程中扮演了暂存运算符的角色。理解了这一层，后面所有关于算法细节的讨论就有了统一的坐标系。
要真正理解逆波兰表达式的价值，必须先回答一个更根本的问题：中缀表达式的麻烦究竟出在哪里。中缀表达式的歧义来源于两个因素，一是运算符之间的优先级差异，二是括号对运算顺序的强制改变。以表达式 a + b c 为例，按照乘除先于加减的优先级规则，正确的运算顺序是先算 b c，再算 a 加上这个乘积。如果计算机不做任何预处理，而是简单地从左到右扫描，它会先看到加号，误以为先执行加法，从而得出错误结果。要让计算机正确处理，就必须在扫描到加号时暂停判断，先看它后面是否有优先级更高的运算符，这就引入了回溯和前瞻的复杂度。
括号的出现进一步加剧了这种复杂性。表达式 (a + b) c 与 a + b c 相比，虽然运算符集合完全相同，仅仅多了一对括号，运算顺序却完全反转：前者先算加法再算乘法，后者先算乘法再算加法。这意味着中缀表达式的求值器必须能够识别括号的嵌套结构，在遇到左括号时把当前状态压栈保存，遇到右括号时弹出恢复，这个压栈弹栈的过程与函数调用的递归结构高度相似，实现起来逻辑分支众多，容易出错。
逆波兰表达式的巧妙之处，在于它把上述所有复杂性一次性消解。因为运算符紧跟操作数之后出现，运算符的作用范围由它出现的位置唯一确定，不需要任何优先级规则来裁决，也不需要任何括号来改写顺序。例如中缀表达式 a + b c 转换为后缀 a b c + 之后，从左到右扫描：先遇到 a、b、c 三个操作数依次入栈，然后遇到乘号，弹出 c 和 b 计算 b * c 得到结果，再遇到加号，弹出这个结果和 a 计算 a 加上乘积，整个求值过程不需要判断任何优先级，也不需要处理任何括号。运算顺序被彻底固化在了运算符的排列顺序之中。
这种固化带来的收益是多方面的。对于编译器而言，逆波兰式可以直接作为中间表示，将高级语言中的算术表达式翻译成后缀形式后，代码生成阶段只需维护一个操作数栈，逐个读取后缀元素并发射指令即可，极大地简化了代码生成器的设计。对于解释器和计算器程序而言，逆波兰式把表达式求值从需要递归下降解析的复杂问题，降维成了一个简单的线性扫描加栈操作的问题。历史上，逆波兰式还直接催生了逆波兰计算器这类硬件设计，操作者按照后缀顺序输入，计算器内部只需一个硬件栈即可完成求值，无需任何优先级判断电路。这些正是逆波兰表达式在计算机领域经久不衰的根本原因。
将中缀表达式转换为后缀表达式的经典算法被称为调度场算法，由计算机科学家艾兹格·迪科斯彻提出，其名字形象地描述了算法中运算符像火车车厢一样在栈中排队等候编组的场景。算法的核心数据结构是一个运算符栈，操作数则直接输出到结果序列。算法从左到右扫描中缀表达式，根据当前读到的字符类型执行不同的动作，其中运算符优先级的处理是算法的关键所在。
当扫描到一个运算符时，不能简单地把它压入栈中，而必须先与栈顶已有的运算符进行优先级比较。具体规则是：如果当前运算符的优先级高于栈顶运算符，则直接将当前运算符压入栈；如果当前运算符的优先级低于或等于栈顶运算符，则需要先把栈顶运算符弹出并输出到结果序列，然后继续与新的栈顶比较，直到栈顶运算符的优先级低于当前运算符，或者栈顶为左括号，或者栈为空，此时才能把当前运算符压入栈。这条规则的直观含义是，栈中的运算符应当始终保持优先级自底向上递增或相等的单调排列，高优先级的运算总是先于低优先级运算输出，从而确保后缀表达式中运算符出现的顺序与真实运算顺序一致。
优先级的具体取值在软考题目中通常约定为：乘除的优先级高于加减，幂运算的优先级又高于乘除。对于同优先级的运算符，如加与减、乘与除，规则采用左结合约定，即左侧先出现、先运算，因此在转换时，遇到同优先级运算符应当把栈顶的运算符弹出输出，再压入当前运算符。以表达式 a - b - c 为例，正确转换应先把第一个减号压栈，输出 b 后扫描到第二个减号，此时栈顶是减号且优先级相同，弹出第一个减号输出，再压入第二个减号，最终得到 a b - c -，对应先算 a - b 再减 c 的正确顺序。
括号在调度场算法中享有特殊地位。左括号不是运算符，它的作用是标记一个子表达式的起始边界。当扫描到左括号时，无论栈顶是什么，都必须无条件地把左括号压入栈中，因为左括号代表一个新的优先级上下文正在开启，它内部的所有运算符都要先于括号外的运算执行。左括号在压栈后，其行为相当于一个优先级极低、低到任何运算符都能压在其上方的哨兵。
右括号则扮演终止符的角色。当扫描到右括号时，说明当前子表达式已经结束，需要把栈中左括号之上的所有运算符依次弹出并输出到结果序列，直到遇到与之匹配的左括号为止，然后将这对括号丢弃。这里的关键在于，左括号和右括号本身都不会出现在输出的后缀表达式中，它们只是转换过程中的辅助标记。如果扫描到右括号时栈中已经找不到匹配的左括号，则说明原表达式的括号不配对，这是一个语法错误，转换应当报错终止。
括号的处理规则还揭示了一个重要事实：括号本质上改变了运算符的压栈时机。以表达式 (a + b) c 为例，扫描到左括号时压入，扫描到 a 输出，扫描到加号时因为栈顶是左括号，加号优先级高于左括号哨兵，直接压栈，扫描到 b 输出，扫描到右括号时弹出加号输出并丢弃括号对，此时输出序列为 a b +，运算符栈为空，再扫描乘号压栈，扫描 c 输出，最后弹出乘号，得到 a b + c 。可以看到，正是左括号的哨兵作用，使得括号内的加号能够先于括号外的乘号被输出，从而实现了运算顺序的强制改变。
为了让转换过程彻底清晰，下面用一个稍复杂的表达式完整演示调度场算法的每一步。取中缀表达式 a + b * (c - d) / e，约定乘除优先级为二级、加减为一级。初始时运算符栈为空，输出序列为空。从左到右扫描，首先读到操作数 a，直接输出，序列变为 a。然后读到加号，此时栈为空，直接压入，栈中为加号。接着读到操作数 b，输出，序列变为 a b。再读到乘号，与栈顶加号比较，乘号优先级高于加号，直接压栈，栈中自底向上为加号、乘号。
继续读到左括号，无条件压栈，栈中为加号、乘号、左括号。读到操作数 c，输出，序列变为 a b c。读到减号，与栈顶左括号比较，左括号是哨兵，减号优先级高于它，直接压栈，栈中为加号、乘号、左括号、减号。读到操作数 d，输出，序列变为 a b c d。读到右括号，开始弹出栈顶运算符输出，直到遇到左括号：先弹出减
本篇完！