[!TIP] 前缀表达式和后缀表达式中，从哪边开始读取，看操作符位置决定从哪边读取.
前缀表达式: 操作符在前，从后往前读取
后缀表达式: 操作符在后，从前往后读取
中缀表达式、前缀表达式和后缀表达式是常见的数学表达式表示方式，它们在运算顺序、优先级、括号的使用方式等方面有所不同。它们的不同形式主要影响计算机如何解析和计算表达式。
1. 中缀表达式（Infix Notation）
中缀表达式是最常见的数学表达式形式，它将操作符放在操作数之间。例如：
A + B
(A + B) * C
特点：
- 运算符位于两个操作数之间。
- 需要括号来明确运算的优先级。
- 需要按照运算符的优先级（如乘法和除法高于加法和减法）来正确解析表达式。
举例：
A + B * C
根据优先级，B * C 会先计算，然后再加上 A。
优点：
- 人类习惯使用中缀表达式。
- 它具有自然的数学符号，可以直观理解。
缺点：
- 需要额外的括号来表示优先级，复杂表达式容易出错。
- 计算机解析时需要优先级和括号规则，因此解析较为复杂。
2. 前缀表达式（Prefix Notation）
从右往左压栈和出栈
前缀表达式，也称为波兰表达式（Polish Notation），是将操作符放在操作数之前。例如：
+ A B
* + A B C
特点：
- 操作符位于操作数之前。
- 不需要括号来标识优先级，运算顺序由操作符的位置决定。
- 从右到左读取表达式时，可以直接进行计算。
举例：
+ A * B C
首先计算 * B C，然后将结果加上 A。
前缀表达式的示例：
假设有一个前缀表达式 * + 5 6 3，我们来演示如何用栈来计算：
步骤 1:
- 栈为空：
[]
步骤 2:
- 读取
3，是操作数，将3压入栈：[3]
步骤 3:
- 读取
6，是操作数，将6压入栈：[3, 6]
步骤 4:
- 读取
5，是操作数，将5压入栈：[3, 6, 5]
步骤 5:
- 读取
+，是操作符，弹出5和6，计算5 + 6 = 11，将结果11压入栈：[3, 11]
步骤 6:
- 读取
*，是操作符，弹出11和3，计算3 * 11 = 33，将结果33压入栈：[33]
结果：
- 最终栈中只剩下
33，这就是整个表达式的结果。
优点：
- 不需要括号。
- 运算顺序明确，可以直接通过栈进行计算。
缺点：
- 人类不习惯这种表示法，比较难以直观理解。
3. 后缀表达式（Postfix Notation）
从左往右压栈和出栈
后缀表达式，也叫逆波兰表达式（Reverse Polish Notation，RPN），是将操作符放在操作数之后。例如：
A B +
A B C * +
特点：
- 操作符位于操作数之后。
- 不需要括号来标识优先级，运算顺序由操作符的位置决定。
- 适合用栈进行计算，避免了括号和优先级的问题。
举例：
A B C * +
首先计算 B * C，然后将 A 和 B * C 相加。
优点：
- 计算机可以通过栈轻松实现，不需要考虑优先级和括号。
- 不需要额外的括号。
- 适合计算机快速计算。
缺点：
- 对人类来说不够直观，需要一些训练来理解。
后缀表达式的计算过程：
- 初始化一个空栈。
- 逐个读取后缀表达式中的元素，如果是操作数（如数字），将其推入栈中。
- 如果是操作符（如 +、-、* 、/），从栈中弹出两个操作数，然后对这两个操作数进行运算，再将结果推回栈中。
- 最终栈中剩下的唯一元素就是表达式的计算结果。
后缀表达式的示例：
假设有一个后缀表达式 5 6 + 3 *，我们来演示如何用栈来计算：
步骤 1:
- 栈为空：
[]
步骤 2:
- 读取
5，是操作数，将5压入栈：[5]
步骤 3:
- 读取
6，是操作数，将6压入栈：[5, 6]
步骤 4:
- 读取
+，是操作符，弹出6和5，计算5 + 6 = 11，将结果11压入栈：[11]
步骤 5:
- 读取
3，是操作数，将3压入栈：[11, 3]
步骤 6:
- 读取
*，是操作符，弹出3和11，计算11 * 3 = 33，将结果33压入栈：[33]
结果：
- 最终栈中只剩下
33，这就是整个表达式的结果。
表达式转换
中缀表达式、前缀表达式和后缀表达式之间可以通过特定的算法转换。最常见的转换方法是“堆栈算法”或“逆波兰记法算法”。 例如，(A + B) * (C + D) 转换为后缀表达式为 A B + C D + *。
应用
-
中缀表达式的应用：
- 人类日常使用：大多数数学计算都以中缀表达式的形式进行。它的优点是易于理解和直观，但对计算机来说解析时会涉及优先级和括号的问题。
-
前缀表达式的应用：
- 编译器优化：前缀表达式经常用于编译器内部的表达式求值，尤其是在语言设计中。
- 图形计算器：某些高级计算器和科学计算器使用前缀表示法来计算表达式。
-
后缀表达式的应用：
- 栈运算：后缀表达式非常适合计算机使用栈来进行计算。后缀表达式可以通过栈来实现，计算机不需要考虑括号或运算符优先级。
- 编译器中的中间表示：许多编译器将表达式转换为后缀表达式来优化求值过程。
- 逆波兰计算器：许多科学计算器（如HP计算器）使用逆波兰表示法。