栈和队列的应用

需能够手工模拟中序和后序表达式的计算过程，包括两者之间的转换，常常在选择题中出现。

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

表达式类型	描述	示例表达式	对应的公式
前序	操作符位于其操作数之前	`* + A B C`	`(A + B) * C`
中序	操作符位于其两个操作数之间，最常见的表示法	`(A + B) * C`	`(A + B) * C`
后序	操作符位于其操作数之后	`A B + C *`	`(A + B) * C`

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

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

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

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

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

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

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