扫码获取 VIP 码
添加管理员微信获取 VIP 码
表达式是程序设计语言中最基础、最核心的语法构件，任何一个能运行的计算机程序，归根结底都在对表达式进行求值。软考软件设计师与系统分析师科目几乎每年都会围绕表达式的表示与求值出一道选择题，而这道题的核心考点，就落在一个看似简单、实则极易出错的问题上：同一个算术表达式，如何用不同的记法表示，以及计算机到底偏爱哪一种记法。
中缀表达式是我们从小学算术开始就熟悉的书写方式，其本质特征是运算符位于两个操作数的中间。例如表达式 A 加 B 写作 A+B，运算符加号被两个操作数 A 与 B 夹在中间，因此得名中缀。中缀表达式的优点一目了然，它符合人类长期形成的阅读与书写习惯，表达式结构一目了然，括号的作用也直观易懂。然而中缀表达式对计算机并不友好，根本原因在于它无法被顺序扫描直接求值，必须先解决运算符优先级与括号匹配这两个额外的问题。
具体而言，当中缀表达式 A+B*C 出现时，计算机按从左到右的顺序扫描，遇到加号时并不能立即执行加法运算，因为它必须回头确认加号右侧是否存在优先级更高的乘法运算。这种需要前瞻与回退的求值方式，与计算机顺序执行的天然机制相冲突，迫使编译器在真正求值之前增加一道额外的转换工序，把中缀表达式先转换为一种可以顺序扫描、无须回溯的形式。
前缀表达式又被称为波兰式，得名于波兰逻辑学家卢卡西维茨在二十世纪二十年代提出的无括号记法体系。其核心规则是运算符写在操作数的前面，例如 A+B 在前缀表达式中写作 +AB，而 A+BC 则写作 +ABC。前缀表达式的显著特点是完全不需要括号，因为运算符一旦确定出现在操作数之前，配合操作数个数已知这一前提，整个表达式的求值顺序就被唯一确定下来，不再存在二义性。
前缀表达式的求值同样采用顺序扫描，但扫描方向是从右向左，遇到操作数就压栈，遇到运算符就从栈中弹出两个操作数进行运算后再压回栈中。这种从右向左的扫描方向，与人类从左向右的阅读习惯相悖，因此前缀表达式虽然在理论上简洁优美，但在实际的教学与考试中出现的频率相对较低，软考更多将其作为概念辨析的干扰项来考查。
后缀表达式又被称为逆波兰式，其命名来源与波兰式一脉相承，因为它的运算符位置恰好与波兰式相反，位于操作数之后。例如 A+B 在后缀表达式中写作 AB+，A+BC 写作 ABC+。后缀表达式同样不需要括号，而且它与前缀表达式相比有一个关键优势：它的求值扫描方向是从左向右，与人类的阅读方向一致，因而在实际的编译技术与计算器实现中应用最为广泛，是软考命题的重中之重。
后缀表达式之所以能去掉括号，本质在于它把运算的执行时机显式地编码进了表达式的书写顺序中。以表达式 (A+B)C 为例，其中缀形式必须借助括号才能表明先算 A+B 再乘以 C，而一旦转换为后缀形式 AB+C，括号就彻底消失，运算的先后关系通过运算符出现的先后位置直接表达出来，计算机从左到右扫描一遍即可完成求值，无须任何优先级判断与括号匹配。
要理解中缀表达式为何能转换为后缀表达式，必须首先理解栈这一数据结构的后进先出特性，以及它是如何天然契合运算符优先级处理这一需求的。栈是一种限定仅在表尾进行插入与删除操作的线性表，允许操作的一端称为栈顶，另一端称为栈底，其核心特征是最后进入的元素最先被取出来，即后进先出原则。
在中缀转后缀的过程中，我们无法在扫描到运算符的瞬间就决定它的输出位置，因为它的右侧可能还有优先级更高的运算符尚未出现。以表达式 A+B*C 为例，当扫描到加号时，加号不能立刻输出，因为后续的乘号优先级更高，必须先处理乘号。这时加号就被暂时存放起来，等待合适的时机再输出。这种需要暂存、暂存后按特定顺序释放的操作，恰好就是栈后进先出特性的完美应用场景。
具体来说，栈中存放的是尚未确定输出时机的运算符。当扫描到一个新的运算符时，需要将它与栈顶运算符的优先级进行比较：若栈顶运算符优先级高于或等于当前运算符，则说明栈顶运算符已经可以确定执行顺序，应当先弹出并输出；若栈顶运算符优先级低于当前运算符，则当前运算符需要压栈等待。这种比较与弹栈、压栈的交替过程，正是栈在后进先出原则下完成运算符优先级排序的底层机制。
括号在中缀表达式中的作用是改变运算符默认的优先级顺序，让括号内的运算先执行。在转换算法中，括号被当作一种特殊的标记来处理：遇到左括号时无条件压栈，作为一层新的优先级边界；遇到右括号时，则持续弹出栈顶运算符并输出，直到遇到与之匹配的左括号为止，然后将这对括号双双丢弃。
这一机制之所以成立，是因为左括号压栈后成为了一道隔离墙，其内部的运算符在栈中形成的后进先出顺序恰好保证了内层括号中的运算先被输出。而一旦右括号出现，栈顶到左括号之间的所有运算符都应当在这个时刻输出，因为它们全部属于当前括号层级内的运算，且已经按优先级排好了顺序。通过这样的弹栈边界设计，括号的嵌套层级被精确地映射为栈中左括号的嵌套深度。
不仅转换过程依赖栈，后缀表达式的求值过程同样依赖栈。后缀求值的规则十分简洁：从左到右扫描表达式，遇到操作数就压入栈中，遇到运算符就从栈中弹出所需数量的操作数，先弹出的作为右操作数，后弹出的作为左操作数，完成运算后将结果重新压回栈中。扫描结束、表达式处理完毕时，栈中恰好只剩下一个元素，这个元素就是整个表达式的最终求值结果。
先弹出作为右操作数、后弹出作为左操作数这一约定，是由后缀表达式的书写顺序决定的。以表达式 AB- 为例，它对应的中缀形式是 A-B，A 先入栈，B 后入栈，因此 B 位于栈顶，弹出时先得到 B 得到的结果顺序恰好对应减法中先弹右、后弹左的规则。对于减法和除法这类不满足交换律的运算，这一顺序约定尤为关键，一旦搞反就会得出符号相反的答案，这也是命题人最爱设置的失分陷阱之一。
表达式转换与求值这一考点在软考中考查的范围相对固定，主要围绕中缀转后缀的算法执行过程、后缀表达式的求值过程以及三种表达式之间的相互辨析展开。掌握了中缀转后缀与后缀求值这两条主线，其余题目基本可以迎刃而解。
中缀表达式转后缀表达式的算法可以概括为以下步骤。第一步，初始化一个运算符栈和一个输出队列，输出队列用于存放转换后的后缀表达式结果。第二步，从左到右逐个扫描中缀表达式的每个字符。第三步，若当前字符是操作数，则直接输出到结果队列。第四步，若当前字符是运算符，则将其与栈顶运算符比较优先级，若栈顶运算符优先级高于或等于当前运算符，则持续弹出栈顶运算符并输出，直到栈为空或栈顶运算符优先级更低，然后将当前运算符压栈。第五步，若当前字符是左括号，则直接压栈。第六步，若当前字符是右括号，则持续弹出栈顶运算符并输出，直到遇到左括号，然后将这对括号丢弃。第七步，扫描结束后，将栈中剩余的所有运算符依次弹出并输出。经过这七步，输出队列中的内容就是最终的后缀表达式。
以中缀表达式 A+BC-D 为例，扫描 A 时直接输出，扫描加号时栈为空直接压栈，扫描 B 时输出，扫描乘号时由于栈顶加号优先级低于乘号，乘号直接压栈，扫描 C 时输出，扫描减号时栈顶乘号优先级高于减号，先弹出乘号输出，再比较栈顶加号，加号与减号优先级相同，弹出加号输出，然后将减号压栈，扫描 D 时输出，扫描结束弹出栈中剩余的减号。最终得到的后缀表达式为 ABC+D-，其求值顺序与中缀表达式完全一致。
后缀表达式求值同样可以概括为清晰的步骤。第一步，初始化一个操作数栈。第二步，从左到右扫描后缀表达式的每个字符。第三步，若当前字符是操作数，则将其压入操作数栈。第四步，若当前字符是运算符，则从栈中弹出两个操作数，先弹出的记为右操作数，后弹出的记为左操作数，执行相应的运算，将结果压回操作数栈。第五步，扫描结束后，操作数栈中剩余的唯一元素即为表达式的值。
以后缀表达式 3 4 + 5 为例，扫描 3 压栈，扫描 4 压栈，遇到加号弹出 4 和 3 计算 3+4 得 7 压栈，扫描 5 压栈，遇到乘号弹出 5 和 7 计算 7
本篇完！