表达式是程序设计语言中最基本的构件之一。我们在日常书写和绝大多数编程语言源代码中使用的是中缀表达式，也就是运算符位于两个操作数之间的写法，例如（a-b）*（c+d），减号写在 a、b 中间，加号写在 c、d 中间，乘号位于两组括号之间。这种写法符合人类阅读习惯，却给计算机处理带来了不小的麻烦：机器必须维护运算符优先级表、处理括号嵌套、判断结合方向，才能确定运算执行顺序。有没有一种写法，能彻底甩掉括号和优先级规则，让表达式从左到右扫一遍就能机械地算出结果？有，这就是逆波兰式。它是软考中级软件设计师上午卷几乎年年必考的知识点，同时与栈、二叉树遍历、编译原理中间代码生成构成完整知识链路，学透它等于一举打通三个模块。
在《数据结构》教材中，逆波兰式的标准定义是：把运算符放在两个操作数之后的表达式表示法，由于运算符位于操作数之后，故又称后缀表达式。与之对应的还有两种表示法：把运算符放在操作数之前的表示法称为前缀表达式，即波兰式；我们日常使用的、运算符夹在两个操作数中间的写法称为中缀表达式。三种表示法表达的是同一个语义，区别仅在于运算符的位置。
以中缀表达式（a-b）（c+d）为例。它的后缀式写作 ab-cd+，从左到右的读法是：先出现操作数 a、b，紧跟其后的减号表示先做 a 减 b；再出现操作数 c、d，紧跟加号表示再做 c 加 d；最后出现的乘号作用于前面已经算出的两个结果。整个表达式没有一对括号，没有任何优先级表，运算次序完全由运算符出现的位置决定。这就是后缀表达式的核心价值：运算顺序被线性化，不再依赖括号和优先级这类上下文信息，计算机只需从左向右扫描一次即可确定全部计算步骤。
前缀式则是相反的方向。同一个表达式的前缀式写作 *-ab+cd，从右向左读：加号作用于它右侧的 c、d，减号作用于它右侧的 a、b，最左侧的乘号作用于两个括号组的运算结果。后缀式适合从左向右扫描求值，前缀式适合从右向左扫描求值，两者都消除了括号，但工程实践中后缀式的使用远比前缀式广泛，原因是计算机按地址递增的顺序访问内存最自然，从左向右扫描与机器指令的执行方向天然一致。
逆波兰这个名称背后有一段真实的技术史。波兰数学家扬·武卡谢维奇在二十世纪二十年代研究数理逻辑时提出了一种免括号的记法，把逻辑运算符写在前缀位置，后人称之为波兰记法。到了五十年代，澳大利亚哲学家兼计算机科学家查尔斯·汉布林重新发掘了这一思想，提出把运算符放到后缀位置的方案，并将其命名为逆波兰记法，英文写作 Reverse Polish Notation，缩写 RPN。所谓"逆"，指的是运算符位置与波兰记法相反，而不是把表达式字符序列倒过来写，这一点是概念题常考的辨析点。
这一记法真正的工程化落地发生在计算器领域。二十世纪六十年代，弗里登公司推出 EC-130 电子计算器，率先采用逆波兰式输入；七十年代，惠普公司的 HP-35 袖珍科学计算器将 RPN 输入方式推广到工程师群体。用 RPN 输入时，操作者先按入操作数、再按运算符，计算器内部只需维护一个栈即可完成全部运算，既不需要括号键，也不需要优先级解析逻辑，硬件实现极其简洁。在存储资源以千字节计数的年代，这种节省是决定性的竞争优势。随后 Forth 语言、PostScript、Java 虚拟机字节码纷纷采用基于操作数栈的后缀式计算模型，逆波兰式从计算器输入法演化为编译器与虚拟机的基础抽象。软考把这个知识点放在数据结构与程序设计语言基础两个模块的交界处考查，考的就是这条从数学记法演进到机器执行模型的完整主线。
理解逆波兰式的关键不在于背诵某个转换结果，而在于理解栈在其中的作用。栈是一种后进先出的线性表，只能在表的一端（栈顶）进行插入和删除。它的操作特性恰好与表达式运算次序的两个特征吻合，正是这种吻合让栈成为表达式处理的天然工具。
先看一个关键观察。在中缀表达式里，运算符的出现顺序与执行顺序经常不一致。例如 a+bc 中，加号先出现、乘号后出现，但执行时先算乘法再算加法；又如 ab/c 中乘除同级，执行顺序与出现顺序一致，从左到右进行。这说明中缀表达式中的运算符序列是延迟决策的序列：一个运算符能不能执行，要等看到它后面的运算符才能确定。栈恰好提供这种延迟机制：暂时无法确定执行时机的运算符先压入栈中，一旦扫描到优先级不高于它的后继运算符，就从栈顶弹出。后进先出的特性保证了正确次序：越是来得早却执行得晚的运算符越靠近栈底，越是来得晚却执行得早的运算符越靠近栈顶，弹出顺序正好是执行顺序。这就是运算符栈存在的最深层理由。
教材给出的转换算法分为五步。第一步，设置一个运算符栈，初始为空，从左到右扫描中缀表达式。第二步，遇到操作数（包括常量与变量）时直接输出到结果串，操作数全程不经过栈。第三步，遇到运算符时与栈顶运算符比较优先级：若栈为空、栈顶为左括号、或者当前运算符的优先级高于栈顶，则当前运算符入栈；否则弹出栈顶运算符输出，并继续与新的栈顶比较，直到满足入栈条件为止。第四步，遇到左括号时无条件入栈；遇到右括号时反复弹出栈顶输出，直到弹出左括号为止，这一对括号本身不进入结果串。第五步，扫描结束后，将栈中剩余运算符依次弹出输出。整个算法没有任何主观判断，全部由栈的机械操作完成。
以（a-b）（c+d）为例完整走一遍。扫描左括号，入栈；扫描 a，直接输出；扫描减号，栈顶是左括号，减号入栈；扫描 b，输出，结果串为 ab；扫描右括号，弹出栈顶减号输出并丢弃左括号，结果串为 ab-；扫描乘号，栈已空，乘号入栈；扫描左括号，入栈；扫描 c，输出；扫描加号，栈顶是左括号，加号入栈；扫描 d，输出；扫描右括号，弹出加号输出并丢弃左括号，结果串为 ab-cd+；扫描结束，弹出剩余乘号，得到 ab-cd+。注意一个细节：右括号的作用是"清场"，把括号范围内尚未输出的运算符全部逼出栈，而左括号入栈后的角色是"挡板"，让任何运算符都可以压到它上面。
优先级表是这套算法的基础。软考范围内只需记住四档关系：乘除高于加减；同优先级运算符之间，后来者要把先来者逼出栈，以此实现从左到右的结合方向；左括号入栈后优先级视为最低，任何运算符都可以压到它上面；栈顶为左括号时，任何新运算符都可以入栈。这四条规则组合起来，就能覆盖软考出现过的全部中缀转后缀题目。
转换得到的后缀式如何求值？与转换过程使用运算符栈不同，求值过程使用的是操作数栈，两个栈的角色必须分清。求值算法是：从左到右扫描后缀表达式，遇到操作数就压栈；遇到运算符就弹出栈顶两个操作数，先弹出的是右操作数，后弹出的是左操作数，执行运算后把结果压回栈中。扫描结束时，栈中剩余的唯一元素就是整个表达式的值。这个弹出次序极其重要：对减法、除法这类不可交换的运算，先弹出的数必须放在运算符右侧，次序颠倒结果就错，这是下午题代码填空的高频空点。
用 ab-cd+* 演示：a 压栈，b 压栈；减号弹出 b、a，计算 a-b 后压回；c 压栈，d 压栈；加号弹出 d、c，计算 c+d 后压回；乘号弹出两个中间结果相乘后压回。扫描结束时栈中只剩一个值，即最终结果。可以看到，整个求值过程完全不需要任何优先级知识，从头到尾一次扫描完成，这是后缀式在机器执行层面最大的优势，也是它被编译器和虚拟机选作中间表示的根本原因。
求值过程还附带合法性检查的副产品：扫描中遇到运算符时栈中不足两个操作数，说明该后缀式非法；扫描结束后栈中剩余多于一个元素，同样非法。命题人有时会把非法后缀式混在选项中，这类选项的特征是某个运算符前面累积的操作数不够，识别这一特征即可快速排除。
逆波兰式与二叉树遍历之间存在一组教科书级的对应关系，软考多次直接以此为命题素材。把中缀表达式画成语法树：操作数都是叶子结点，运算符都是内部结点，优先级高的运算位于树的下层，括号控制的是子树的分组方式。对同一棵语法树分别做前序、中序、后序遍历，得到的结点序列恰好对应前缀式、中缀式、后缀式三种表示法。
以（a-b）（c+d）的语法树为例：乘号是根，左子树以减号为根（叶子 a、b），右子树以加号为根（叶子 c、d）。前序遍历按根、左、右输出：乘号，左子树减号，叶子 a、b，右子树加号，叶子 c、d，整体为 -ab+cd，正是前缀式。中序遍历按左、根、右输出，得到 a 减 b、乘、c 加 d 的次序，即去掉括号的中缀式内容——注意若不加括号，中序序列直接拼接会丢失优先级信息，这正是中缀式必须依赖括号和优先级表的根本原因。后序遍历按左、右、根的次序输出：先输出左子树的 ab 和减号，再输出右子树的 cd 和加号，最后输出根结点的乘号，整体序列为 ab-cd+*，正是后缀式。
这组对应关系揭示了后缀式的本质：后缀式就是语法树的后序遍历序列。运算符作为根结点，它的输出被推迟到左右子树全部输出完毕之后，自然形成操作数在前、运算符在后的形态。理解了这一层，遇到给语法树求后缀式的题目直接做后序遍历即可；反过来，它也解释了后缀式为什么能无歧义求值：后序遍历序列配合操作数栈，等价于对语法树做自底向上的归约计算，叶子先算、内部结点后算，与语法树语义天然一致。
中缀式、前缀式、后缀式构成一个完整的谱系，各有明确的适用边界。中缀式的优点是符合人的阅读习惯，缺点是必须配备优先级表和括号规则，计算机解析时需要先完成词法分析与语法分析，实现成本高；它的应用场景是程序源代码和人机交互界面，几乎所有程序设计语言的源程序都采用中缀式书写。前缀式消除
本篇完！