扫码获取 VIP 码
添加管理员微信获取 VIP 码
软考软件设计师和系统架构设计师的上午题里，几乎每年都会出现一道关于后缀表达式的题目。题干往往只给一个中缀表达式，要求考生写出它对应的后缀式，或者反过来给一个后缀式，要求考生写出求值过程。这道题的分值不高，通常只有一两分，却是很多考生反复丢分的重灾区。丢分的根源不在于不会背概念，而在于没有真正理解栈这个数据结构在后缀表达式处理中扮演的角色。很多考生把后缀表达式当成一道死记硬背的语法题，考前突击背一遍转换口诀就上考场，结果一旦遇到嵌套括号、连续同优先级运算符或者减法除法这类非交换运算，立刻方寸大乱。本篇文章从后缀表达式的形式化定义出发，沿着中缀转后缀的转换算法和逆波兰式求值两条主线逐层拆解，把运算符优先级、结合性、括号处理这些最容易混淆的细节一次讲透，最后落到历年真题的命题思路上，帮助考生把这道送分题稳稳拿到手，不留任何知识死角。
在讨论后缀表达式之前，必须先厘清表达式的三种书写形式。同一个算术表达式，根据运算符相对于操作数的位置不同，可以分为中缀、前缀和后缀三种记法。考生若分不清这三种记法的本质区别，后面所有关于转换和求值的讨论都会失去根基，变成空中楼阁。这一节的目标，是让读者能够一眼说出任意一个表达式属于哪一种记法，并理解后缀表达式最核心的性质。
中缀表达式是我们从小学开始就接触的写法，运算符位于两个操作数之间。例如 A 加上 B 写作 A+B，加号正好夹在 A 和 B 的中间，这就是"中缀"二字的由来。这种写法符合人类的阅读直觉，几乎所有日常的数学书写都采用这种形式，但它有一个致命的缺陷，那就是必须依赖运算符优先级和括号，才能无歧义地确定运算顺序。比如表达式 A+BC，仅凭字面是无法确定先做加法还是先做乘法的，需要额外约定乘法优先于加法；若要改变这个默认顺序，还必须借助括号，写成 (A+B)C 才能表达先加后乘的意图。
后缀表达式又称逆波兰式，得名于波兰逻辑学家卢卡西维茨。它的特点是运算符紧跟在两个操作数之后，例如 A 加上 B 写作 AB+，加号跟在 A 和 B 的后面。在后缀表达式中，运算符的先后顺序天然地对应了运算的执行顺序，因此完全不需要括号，也不需要优先级规则，从左到右扫描一遍就能唯一地确定求值过程。前缀表达式与之相对，运算符位于两个操作数之前，例如 A 加上 B 写作 +AB，同样不需要括号。
这三者的关系可以用一个简单的式子统一观察。对于中缀表达式 A+BC，按照乘法优先的约定，等价的后缀表达式是 ABC+，等价的前缀表达式是 +A*BC。可以看到，后缀式和前缀式都彻底消灭了括号，把运算顺序固化到了符号的排列顺序里。这个"固化"的过程，正是理解三种记法差异的关键所在：中缀式把运算顺序藏在优先级规则里，而后缀式和前缀式把运算顺序摆在明面上。
从数据结构的视角看，后缀表达式可以严格定义为一个运算符和操作数组成的序列，该序列满足这样一个性质：从左到右扫描时，任意时刻已经出现的操作数个数，始终大于已经出现的运算符个数，直到序列末尾，操作数比运算符恰好多一个。这个性质保证了每一个运算符都能在它出现之前找到足够的操作数与之配对。以 AB+ 为例，扫描到 A 时操作数为一，扫描到 B 时操作数为二，扫描到加号时操作数比运算符恰好多一个，满足配对条件。
这一性质并非可有可无的形式约束，而是后缀表达式能够被机械求值的充要条件。它直观地说明了为什么后缀式不需要括号，因为括号的作用本来是改变运算的先后，而后缀式把"谁先算、谁后算"直接编码进了符号出现的顺序里，括号自然就失去了存在的意义。反过来理解，任何满足上述计数性质的运算符与操作数序列，都可以唯一地还原成一个确定的运算过程，不会产生二义性。
"逆波兰式"这个名称本身就带有值得深挖的信息。卢卡西维茨最初提出的是前缀记法，也就是波兰记法，因为运算符写在操作数之前。后人把运算符挪到操作数之后，相当于把波兰记法"反过来"，于是得名逆波兰式。名称虽然简单，却提示了一个重要的事实：后缀式与前缀式本质上是同一种思想的两种镜像，都是通过符号位置来消除括号与优先级。理解了这个名称渊源，考生就不会把逆波兰式当成一个孤立的需要死记的怪名词，而是能把它纳入"无括号表达式"这个更大的知识框架里。
理解了后缀表达式的定义之后，下一步要回答的问题就是，计算机究竟是如何高效地求值一个后缀表达式的，以及中缀表达式又是如何被转换成后缀式的。这两个问题的答案都指向同一个数据结构，那就是栈。栈之所以能胜任这两项工作，根本原因在于后缀表达式和转换过程都呈现出强烈的后进先出特征，而栈正是为后进先出量身定做的容器。
栈是一种后进先出的线性结构，只允许在一端进行插入和删除操作。插入操作称为入栈或压栈，删除操作称为出栈或弹栈，这一端称为栈顶，另一端称为栈底。最先入栈的元素被压在栈底，最后入栈的元素位于栈顶，因此最后入栈的元素必然最先被取出，这就是后进先出的含义。栈在计算机科学中的地位极为特殊，函数调用的现场保护、递归的执行、括号匹配、表达式求值，无一不是借助栈来实现的，后缀表达式只是栈众多应用中的一个典型代表。
后缀表达式求值之所以选择栈，是因为它的运算规则天然呈现出后进先出的特征：遇到运算符时，需要操作的是最近出现的两个操作数，而这两个操作数恰好位于当前待处理序列的最末端。求值过程可以归纳为一句完整的话：从左到右依次扫描后缀表达式的每个符号，若扫描到操作数，则将其压入栈中；若扫描到运算符，则从栈中弹出两个操作数，先弹出的作为右操作数，后弹出的作为左操作数，执行运算后把结果重新压回栈。当整个序列扫描完毕，栈中剩下的唯一元素就是整个表达式的值。
这里有一个极易被忽略却至关重要的细节，就是弹出顺序与操作数位置的对应关系。对于加法和乘法这类满足交换律的运算，操作数的左右顺序不影响结果，因此很多考生从来不去区分先弹出的是左操作数还是右操作数。但一旦遇到减法和除法，顺序颠倒就会直接导致结果符号相反。规范的规则是，后弹出的操作数是左操作数，先弹出的操作数是右操作数。以减法后缀式 AB- 为例，先弹出的是 B，后弹出的是 A，因此应当计算 A-B，而不是 B-A。这个细节在命题人设计陷阱时经常被利用，务必牢记。
求值相对直观，转换则要复杂得多。将中缀表达式转换为后缀表达式的经典算法需要借助一个运算符栈，同时维护一套严格的入栈和出栈规则。算法的大致流程是：从左到右扫描中缀表达式的每个符号，遇到操作数就直接输出到结果串中；遇到运算符时，先把它与栈顶运算符比较优先级，若当前运算符优先级高于栈顶，则直接入栈，否则反复弹出栈顶运算符并输出，直到栈顶优先级低于当前运算符，再把当前运算符入栈；遇到左括号直接入栈，遇到右括号则不断弹出栈顶运算符输出，直到弹出与之配对的左括号为止。
这套规则的核心在于一个不等号的判定，即比较的是"当前运算符"与"栈顶运算符"之间的优先级高低关系。命题人经常在这一点上设置迷惑项，比如把比较方向写反，或者把"高于才入栈"写成"不低于就入栈"，后者会破坏同类运算符从左到右的结合性。考生必须把这个判定条件理解到可以默写的程度，而不是模模糊糊记住一个"高入低出"的大意。
优先级表是转换算法的灵魂，考生必须准确记忆一套统一的优先级序列。通常约定乘除的优先级高于加减，乘方高于乘除，括号具有最高优先级的"特权"。但仅有优先级还不够，还必须约定同优先级运算符的结合方向。结合性解决的是连续出现同优先级运算符时先算谁的问题。加减乘除都是左结合，也就是从左到右依次计算，因此 A-B-C 应理解为 A-B 的差再减 C。而在转换算法中，左结合体现为：当前运算符的优先级小于或等于栈顶运算符时就要弹栈。这个"等于"两个字正是保证左结合的关键，丢掉它，同类运算符的先后顺序就会颠倒。乘方则是右结合的特例，这在软考中偶有涉及，考生了解即可，不必过度纠结。
后缀表达式不是一个孤立的考题概念，它在真实软件系统中有着非常具体的位置。理解它的应用场景，能反过来帮助考生在考场上下意识地调用正确的算法记忆。这一节把三种表达式的相互转换关系理清，再把后缀式放回编译原理和计算器实现的真实语境中，让读者看到这个考点背后的工程意义。
中缀、前缀、后缀三种记法之间理论上可以两两转换，但软考命题集中在两个方向上：中缀转后缀，以及后缀式求值。前缀式虽然也出现在个别年份，但考查频率远
本篇完！