扫码获取 VIP 码
添加管理员微信获取 VIP 码
在计算机科学与编译原理的语境里，表达式记法解决的是一个核心问题：一个由操作数与运算符组成的式子，究竟按照什么顺序书写、又按照什么顺序被机器理解。软考《数据结构》与《编译原理》相关章节中，把表达式划分为三种标准记法，分别是中缀表达式、前缀表达式与后缀表达式。
中缀表达式是人们在数学课堂上最熟悉的形式，运算符写在两个操作数的中间，例如 a-b、a+b*c。它的最大特点是符合人类的阅读习惯，但它隐含着两个麻烦：一是运算符优先级需要额外约定，二是运算顺序需要借助括号来改变。当计算机直接解析中缀表达式时，必须先做优先级判断与括号匹配，这个解析过程并不直观。
前缀表达式又称波兰式，运算符写在操作数之前。例如中缀式 a-b 对应的前缀式是 -ab，中缀式 a+bc 对应的前缀式是 +abc。前缀表达式的运算规则是：从右向左扫描，遇到运算符就取出它后面最近的两个操作数先运算。由于运算符总在操作数之前，前缀式天然不含括号，也天然不含优先级歧义。
后缀表达式又称逆波兰式，运算符写在操作数之后。例如中缀式 a-b 对应的后缀式是 ab-，中缀式 a+bc 对应的后缀式是 abc+。后缀表达式的运算规则是：从左向右扫描，遇到运算符就取出它前面最近的两个操作数进行运算。与前缀式一样，后缀式彻底消除了括号与优先级的需要，让运算顺序完全由书写顺序决定。
这三种记法在本质上是同一棵表达式的三种不同遍历结果。若把中缀表达式画成一棵表达式树，操作数位于叶子结点，运算符位于内部结点，那么对同一棵树分别做中序遍历、前序遍历与后序遍历，恰好得到中缀式、前缀式与后缀式。这一点是理解三种记法之间转换关系的根本枢纽，也是软考命题人在选择题中反复利用的底层逻辑。
逆波兰式的名称来源于波兰逻辑学家扬·武卡谢维奇。二十世纪二十年代，武卡谢维奇在研究命题逻辑时提出了一种无需括号的记法体系，其初衷是让逻辑表达式可以完全摆脱括号，从而简化形式化推理。他的本意是把运算符前置，即今天所称的前缀式。后来，在计算机科学的实践中，人们发现把运算符后置的形式对求值更加友好，因为机器只需从左到右线性扫描一遍即可完成计算，这种后置形式便被称为逆波兰式，以区别于武卡谢维奇最初的前缀方案。
逆波兰式在计算机发展史上有着明确的工程地位。早期计算器，尤其是惠普公司在二十世纪七十年代推出的系列科学计算器，大量采用了逆波兰输入方式，用户先输入操作数再输入运算符，计算器内部只需维护一个栈即可完成任意复杂表达式的求值，无需记忆运算符优先级，也无需处理括号。这一工程选择深刻地说明了一个事实：逆波兰式之所以被计算机采用，不是因为它在书写上更优雅，而是因为它能把表达式的求值过程简化为一个极其规整的线性扫描加栈操作的过程。
在软考的知识体系中，逆波兰式的定位是中缀表达式求值问题的一个标准解法，同时也是编译原理中语义处理阶段的一个基本概念。软件设计师、系统分析师等科目的历年真题中，逆波兰式通常以两种面貌出现：一是给定中缀表达式求其对应的后缀式，二是给定后缀表达式求其运算结果，两种考法的底层都指向同一个算法——借助栈完成中缀到后缀的转换，以及借助栈完成后缀式的求值。
把中缀表达式转换为后缀表达式，是整个知识点中最容易出错、也是命题人最爱挖坑的环节。其标准算法可以概括为一条主流程与两条分支规则。主流程是：从左到右依次扫描中缀表达式的每个符号，根据符号类型分别处理。当扫描到操作数时，直接输出到结果串；当扫描到运算符时，将其与栈顶运算符比较优先级后决定入栈或出栈；当扫描到左括号时，直接入栈；当扫描到右括号时，持续弹出栈顶元素输出，直到遇到与之配对的左括号，并把这对括号一并丢弃。
运算符的处理规则需要格外精确。遇到一个运算符时，反复比较它与栈顶运算符的优先级：若栈顶运算符的优先级大于或等于当前运算符的优先级，则弹出栈顶运算符并输出，然后继续比较新的栈顶；若栈顶运算符的优先级小于当前运算符，则把当前运算符压入栈中。这里最关键的一个细节是"大于或等于"中的"等于"，它体现的是运算符的结合性。对于左结合的常规运算符，如加、减、乘、除，当新来的运算符与栈顶优先级相等时，必须先弹出栈顶，因为左边的运算要先于右边执行。软考真题中不少错误选项，恰恰就是在优先级相等时错误地让新运算符直接入栈而导致的。
运算符优先级在软考语境下有约定俗成的层次：乘除高于加减，括号内的内容优先处理。更完整的优先级链还应包含幂运算与一元运算符，但软考软件设计师的选择题通常只涉及加减乘除与括号，因此备考时优先掌握这四类运算符加括号即可覆盖绝大多数命题场景。需要强调的是，括号在转换过程中扮演的角色是"临时提升优先级"的标记，它本身不会被输出到结果串中，只负责控制运算符的进出栈时机。
以一个具体式子为例可以完整呈现上述规则。对中缀式 a+bc 做转换：扫描 a，操作数，直接输出，结果串为 a；扫描加号，栈空，入栈；扫描 b，输出，结果串为 ab；扫描乘号，栈顶加号优先级低于乘号，乘号入栈；扫描 c，输出，结果串为 abc；扫描结束，将栈中剩余运算符依次弹出输出，得到 abc+。这个结果对应中缀式 a+(b*c)，与直觉一致，乘法先算，加法后算，运算顺序由后缀式从左到右自然呈现。
后缀表达式的求值是一个比转换更简单、更机械的过程，因此也更容易在考场上被用来考察对栈结构本质的理解。其算法是：从左到右扫描后缀表达式的每个符号，遇到操作数就压入栈中；遇到运算符时，从栈中弹出两个操作数，先弹出的作为右操作数，后弹出的作为左操作数，执行运算后把结果重新压入栈。扫描结束后，栈中剩下的唯一元素就是整个表达式的值。
这里有一个必须牢牢记住的顺序问题：先弹出的操作数是右操作数，后弹出的是左操作数。这个顺序在加法和乘法这类满足交换律的运算中不产生影响，但在减法和除法中一旦颠倒就会得到完全错误的结果。软考的命题人深知这一点，因此常在后缀式求值题中刻意使用减法或除法，用以甄别考生是否真正理解了弹出顺序与运算顺序之间的对应关系。以后缀式 ab- 为例，栈中先压入 a，再压入 b，遇到减号时先弹出 b 作为右操作数，再弹出 a 作为左操作数，结果为 a-b，与中缀式的语义一致。
后缀式求值之所以不需要任何优先级判断，是因为运算符出现的顺序已经蕴含了运算的先后顺序。在左结合的常规语义下，后缀式中越早出现的运算符越早执行，这正好与"从左到右扫描"的求值方向吻合。这种"书写顺序即运算顺序"的性质，是后缀式与中缀式最根本的区别，也是理解为什么编译器和计算器偏爱后缀式的关键。
栈之所以成为表达式转换与求值中不可替代的工具，根源在于表达式的运算顺序具有天然的嵌套结构。在带括号的中缀表达式里，最内层的括号内容最先运算，最外层的运算最后执行，这种"后进先出"的次序恰好与栈的操作特性完全一致。当算法扫描到左括号时把运算符压入栈，扫描到右括号时再从栈顶依次弹出，正是用栈的先进后出特性来重现括号的嵌套匹配关系。
从更抽象的角度看，表达式的求值顺序对应着表达式树的后序遍历结果。表达式树的递归定义决定了子树的运算必须先于父结点完成，而后序遍历的访问顺序恰好保证了"先访问子结点、最后访问根结点"。栈作为递归的显式实现工具，天然适合模拟后序遍历。中缀转后缀的栈算法，本质上就是在不显式构造表达式树的情况下，用栈的进出顺序模拟了中序遍历到后序遍历的转换；后缀式求值的栈算法，则是直接对后序遍历序列执行了自底向上的计算。理解了这一层对应关系，整个知识点就从"死记算法"上升为"结构驱动的自然结果"。
表达式按照运算对象的性质可以划分为算术表达式、逻辑表达式与关系表达式。算术表达式以数值为运算对象，以加减乘除为基本运算符；逻辑表达式以真值或布尔变量为运算对象，以与、或、非为基本运算符；关系表达式则以比较运算为核心。三者在后缀式问题上遵循完全相同的处理框架，区别仅在于运算符集合与优先级层次不同。
对于逻辑表达式，与运算、或运算、非运算同样可以定义优先级，通常非运算最高，与运算次之，或运算最低，并且与、或运算满足各自的结合律。将逻辑表达式转换为后缀式的算法与算术表达
本篇完！