栈和队列的应用

表达式种类

前序表达式（Preorder，也叫做波兰表示法）、中序表达式（Infix）和后序表达式（Postorder, 也称为逆波兰表示法）都是二叉树的遍历策略，通常用于算术表达式的表示。不同的表示方法对操作符和操作数的顺序有不同的规定。

上图是表达式 (A + B) * C 对应的二叉树，前序、后序表达式分别是对这棵树的 前序遍历和后序遍历。

中序表达式求值

中序表达式求值涉及到两个主要的数据结构：操作符栈与操作数栈。其核心思路是逐个读取中序表达式的字符，根据字符的类型（操作数、操作符、括号）进行不同的处理，最终得到表达式的值。

1. 初始化两个栈：
   • 操作数栈：用来存储数字。
   • 操作符栈：用来存储操作符和左括号。
2. 逐个读取中序表达式的字符：
   • 如果是 操作数（数字），则直接压入操作数栈。
   • 如果是 左括号，则直接压入操作符栈。
   • 如果是 右括号，则：
     • 从操作符栈中弹出一个操作符。
     • 从操作数栈中弹出所需的操作数。
     • 执行该操作符对应的运算。
     • 将结果压入操作数栈。
     • 重复以上步骤，直到从操作符栈中弹出一个左括号。
   • 如果是操作符（如+、-、*、/等）：
     • 如果操作符栈为空，或栈顶是左括号，或当前操作符优先级高于栈顶操作符的优先级，则直接压入操作符栈。
     • 否则：
       • 从操作符栈中弹出一个操作符。
       • 从操作数栈中弹出所需的操作数。
       • 执行该操作符对应的运算。
       • 将结果压入操作数栈。
       • 重复以上步骤，直到满足上述的压栈条件。
3. 处理完所有字符后：
   • 如果操作符栈不为空，则：
     • 从操作符栈中弹出一个操作符。
     • 从操作数栈中弹出所需的操作数。
     • 执行该操作符对应的运算。
     • 将结果压入操作数栈。
     • 重复以上步骤，直到操作符栈为空。
4. 得到结果：
   • 此时，操作数栈中仅存一个数字，这就是整个中序表达式的值。

以表达式 3 + (5 * 2 - 8) 说明计算过程：

后序表达式求值

后序表达式求值主要依赖一个操作数栈。其核心思路是逐个读取后序表达式的元素，并根据元素的类型（操作数或操作符）进行处理。

1. 初始化一个操作数栈：
   • 用于存储后序表达式中的数字。
2. 逐个读取后序表达式的元素：
   • 如果是操作数，则直接压入操作数栈。
   • 如果是操作符（如+、-、*、/等）：
     • 从操作数栈中弹出所需的操作数。注意，因为操作符是后置的，所以先弹出的数字是第二操作数，后弹出的是第一操作数。
     • 根据操作符执行相应的运算。
     • 将计算结果压入操作数栈。
3. 完成后序表达式的读取：
   • 操作数栈中的顶部元素即为整个后序表达式的值。

以表达式 3 5 2 * 8 - + 说明计算过程：

中序转后序

将中缀表达式转换为后缀表达式的算法思想如下：

初始化一个操作符栈，从左向右开始扫描中缀表达式；

• 遇到数字时，加入后缀表达式；
• 遇到运算符时：
  • 若为＇（＇，入栈；
  • 若为＇）＇，则依次把栈中的运算符加入后缀表达式中，直到出现＇（＇，从栈中删除＇（＇；
  • 若为除括号外的其他运算符
    • 当其优先级高于除＇（＇以外的栈顶运算符时，直接入栈；
    • 否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。

以中序表达式 a/b+(c*d-e*f)/g 为例，可以通过如下步骤将其转换为后续表达式：

入栈出栈序列

入栈出栈是常考的问题，这类问题的核心可以被总结为如下范式：

给定一个元素入栈序列，判断哪些出栈序列是不可能的？

给定一个入栈序列，其出栈序列可能有很多种，因为一个元素的出栈时间比较灵活，比如它可以一入栈马上出栈，也可以等一会再出栈。要辨别不可能的出栈系列，需要抓住关键规则：只有栈顶元素能够最先出栈。

也就是说，对于下图这种情况，A 被 B 压住了，在出栈序列中，A 一定在 B 的后面。如果某个出栈序列中 A 在 B 的前面，则这种出栈序列是不可能出现的。