在软考软件设计师的考试大纲里，栈（Stack）与队列（Queue）并列为线性结构的两大基础考点，其中栈因为其"后进先出"（Last In First Out，简称 LIFO）的操作特性，成为命题人反复挖掘的对象。所谓栈，指的是限定仅在表尾进行插入和删除操作的线性表，这个被限定操作的一端称为栈顶（top），另一端称为栈底（bottom）。从数据结构的角度看，栈是一种操作受限的线性表，它的"受限"恰恰是其价值所在：正因为插入和删除只能发生在栈顶这一端，元素进出的顺序才被严格约束为后进先出，这种约束为许多需要"逆序处理"的场景提供了天然的实现基础。
栈的基本操作可以归结为四类：入栈（push），把一个新元素压入栈顶；出栈（pop），把栈顶元素删除并返回其值；取栈顶元素（getTop），只读取栈顶元素而不删除；判空（isEmpty），判断栈中是否还有元素。软考选择题里关于栈的题目，绝大多数都围绕这四个操作展开，其中又以"入栈序列与出栈序列"的关系最为经典。对于一个初始为空的栈，若依次压入元素 a、b、c，那么可能的出栈序列并不是任意的，因为后进先出的约束决定了后压入的元素必须先弹出，这一条规则是后续所有表达式求值题目的底层根基。
需要特别指出的是，栈在计算机科学中的地位远不止一道数据结构题。操作系统中函数调用的现场保护与恢复依赖的是系统栈（调用栈），表达式求值器把中缀表达式转换为后缀表达式依赖的是运算符栈和操作数栈，递归算法的执行过程本身就是对栈的隐式调用。理解栈的后进先出特性，是理解这一切的前提。命题人在考察栈时，往往不会只考栈的定义本身，而是把栈嵌入到一个具体的应用场景中去考，表达式求值就是其中出现频率最高的应用场景。
要理解表达式求值，必须先厘清三种表达式写法之间的区别。我们日常书写的算术表达式，运算符位于两个操作数之间，例如"10×(40-30÷5)+20"，这种写法称为中缀表达式（Infix Notation）。中缀表达式符合人类的阅读习惯，但它有一个致命的缺点：运算符的优先级和括号的存在，使得计算机无法按从左到右的顺序直接求值，必须先扫描一遍确定运算的先后次序，这就给机器处理带来了额外的复杂度。
为了解决这个问题，波兰逻辑学家卢卡西维奇（Jan Łukasiewicz）在二十世纪二十年代提出了不用括号也能无歧义地表示运算顺序的写法。其中把运算符放在操作数前面的写法称为前缀表达式，也叫波兰式（Polish Notation）；把运算符放在操作数后面的写法称为后缀表达式，也叫逆波兰式（Reverse Polish Notation，简称 RPN）。这三种写法对同一个表达式的表示结果虽然不同，但表达的含义完全等价。
以表达式"a-b×c"为例。它的中缀形式是"a-b×c"，因为乘法的优先级高于减法，所以先算 b×c，再算 a 减去这个结果。它的后缀形式是"a b c × -"，读法是从左往右扫描：遇到操作数 a 入栈，遇到操作数 b 入栈，遇到操作数 c 入栈，遇到运算符 × 弹出 c 和 b 计算 b×c 得到结果入栈，最后遇到运算符 - 弹出结果和 a 计算 a-(b×c)。可以看到，后缀表达式不需要括号，也不需要约定优先级，因为运算符出现的顺序本身就隐含了运算的先后关系，这正是后缀表达式在编译器和计算器中得到广泛应用的根本原因。
软考对这三种表达式的考察，主要集中在两个方向上：其一是给出一个中缀表达式，要求写出它的后缀式（逆波兰式）；其二是给出一个中缀表达式，要求计算用栈求值过程中操作数栈的最小容量。这两个方向看似独立，本质上都建立在同一个转换算法之上，掌握了算法，两道题就都迎刃而解。
中缀表达式转换为后缀表达式的过程，本质上是对运算符进行"调度"的过程。转换算法的核心思想可以概括为一句话：遇到操作数直接输出，遇到运算符则先与栈顶运算符比较优先级，决定是入栈还是弹出。具体而言，算法需要维护一个运算符栈，然后从左到右扫描中缀表达式的每一个字符，按照以下规则处理。
当扫描到操作数时，直接输出到后缀表达式的结果序列中。当扫描到运算符时，若运算符栈为空或者栈顶是左括号，则当前运算符直接入栈；否则，将当前运算符与栈顶运算符比较优先级，若当前运算符优先级高于栈顶，则直接入栈，若当前运算符优先级不高于栈顶，则反复弹出栈顶运算符并输出，直到栈顶运算符的优先级低于当前运算符为止，然后再把当前运算符入栈。当扫描到左括号时，直接入栈；当扫描到右括号时，反复弹出栈顶运算符并输出，直到弹出左括号为止，左右括号本身都不输出。
这里有几个细节是命题人最喜欢做文章的。第一是优先级的高低判断。在转换算法中，乘法和除法属于同一优先级且高于加法和减法；同优先级运算符之间遵循"左结合"规则，即先出现的运算符优先出栈。第二是左括号的特殊地位。左括号在栈外时优先级最高，任何运算符都能压到它上面；但左括号一旦入栈，它的优先级就变为最低，只有右括号能把它弹出来。第三是负号与减号的区分，这一点在考试中偶有涉及，考生需要根据上下文判断。
以表达式"(a-b)×(c+d)"为例，转换过程如下。扫描到左括号入栈，扫描到 a 输出，扫描到减号时栈顶是左括号所以直接入栈，扫描到 b 输出，扫描到右括号时反复弹栈直到左括号，于是减号被弹出输出，左右括号丢弃。此时结果序列是"a b -"。接着扫描到乘号，栈为空直接入栈，扫描到左括号入栈，扫描到 c 输出，扫描到加号时栈顶是左括号所以入栈，扫描到 d 输出，扫描到右括号弹栈输出加号，结果序列变为"a b - c d +"。最后扫描结束，把栈中剩余的乘号弹出输出，得到最终后缀式"a b - c d + ×"。这就是该表达式后缀式（逆波兰式）的标准答案，也是历年真题反复出现的那一类题目。
得到后缀表达式之后，求值就变得机械而简单，因为后缀表达式天然就是为栈计算而设计的。求值算法只需要一个操作数栈：从左到右扫描后缀表达式的每一个字符，遇到操作数就入栈，遇到运算符就从栈中弹出两个操作数，先弹出的作为右操作数，后弹出的作为左操作数，按运算符计算后把结果压回栈中。扫描结束时，栈中剩下的唯一元素就是整个表达式的值。
这里必须强调操作数的弹出顺序。对于加法和乘法这类满足交换律的运算符，先弹出还是后弹出作左操作数结果相同；但对于减法和除法这类不满足交换律的运算符，顺序错就全盘皆错。标准规则是：后弹出的操作数作为左操作数，先弹出的操作数作为右操作数。比如后缀式"a b -"对应的是 a-b，而不是 b-a，原因就在于 b 先入栈后出，a 后入栈先出，先弹出的是 b，它是减号右边的操作数。
回到软考真题"利用栈对算术表达式10×(40-30÷5)+20求值，存放操作数的栈容量至少为多少"这道题。我们先把中缀表达式转换为后缀表达式，再逐步模拟操作数栈的变化。转换得到后缀式为"10 40 30 5 ÷ - × 20 +"。开始求值：压入 10，栈深为 1；压入 40，栈深为 2；压入 30，栈深为 3；压入 5，栈深为 4；遇到 ÷，弹出 5 和 30，计算 30÷5 得 6，压回 6，此时栈中为 10、40、6，栈深为 3；遇到 -，弹出 6 和 40，计算 40-6 得 34，压回 34，此时栈中为 10、34，栈深为 2；遇到 ×，弹出 34 和 10，计算 10×34 得 340，压回 340，栈深为 1；压入 20，栈深为 2；遇到 +，弹出 20 和 340，计算 340+20 得 360，压回 360，栈深为 1。整个过程中操作数栈的最大深度出现在压入 5 之后，也就是栈深达到 4 的那一刻，因此栈的最小容量是 4，正确答案为选项中的 4。这道题的关键在于，求栈的最小容量就是要找到求值全过程中"同时驻留在栈里的操作数和中间结果最多时"的那个峰值时刻。
表达式求值之所以用栈，与函数调用之所以用栈，背后是同一个道理：都需要后进先出地保存"尚未完成的工作"。在函数调用机制中，每当一个函数被调用，系统就会在调用栈上压入一个栈帧（Stack Frame，也叫活动记录），这个栈帧保存了函数的局部变量、返回地址和参数；当函数返回时，栈帧弹出，控制权交还给调用者。递归函数每深入一层，就会压入一个新的栈帧，这正解释了为什么递归深度过大会导致栈溢出。
把这个机制与表达式求值对照着看，会发现惊人的同构性。中缀表达式中的括号和运算符优先级，本质上就是在描述一种"嵌套的计算结构"：内层括号里的子表达式必须先算完，外层才能继续，这与递归的"先深入后返回"完全一致。后缀表达式之所以能消除括号，正是因为把这种嵌套结构"展平"成了一条线性序列，让栈能够机械地处理。理解了这一层，考生就会明白，后缀表达式并不是一种人为生造的怪异写法，而是编译器在把人类可读的中缀写法翻译成机器可执行的指令序列时的中间产物，栈是连接这两者的桥梁。
表达式求值是栈最典型的应用，也是软考考察栈时最偏爱的载体。在实际的编译器与解释器实现中，表达式求值通常要经过词法分析、语法分析、语义分析和代码生成等阶段，而中缀转后缀、后缀求值这两个环节就是语法分析阶段的核心工作。编译器前端把源程序中的中缀表达式转换为后缀表达式，再翻译成目标机器上的
本篇完！