C++ 如何使用栈求解中缀、后缀表达式的值

C++ 中，我们可以使用栈来求解中缀表达式的值或者先将中缀表达式转换为后缀表达式再进行求解。下面我将演示如何使用栈求解中缀表达式的值和后缀表达式的值。

求解中缀表达式的值

步骤

1. 创建两个栈，一个用于存储操作数，另一个用于存储运算符。
2. 从左到右遍历中缀表达式。
3. 如果当前字符是数字，则入操作数栈。
4. 如果当前字符是运算符，则与运算符栈中的栈顶运算符比较，如果当前运算符的优先级大于栈顶运算符，则将当前运算符入运算符栈；否则从运算符栈中弹出一个运算符，从操作数栈中弹出两个操作数，计算后将结果入操作数栈，继续比较。
5. 重复步骤 3 和 4 直到表达式遍历结束。
6. 从操作数栈中弹出最终结果。

示例

假设我们要求解中缀表达式 1 + 2 * 3 - 4 / 2。

1. 初始化两个栈：操作数栈和运算符栈。
2. 从左到右遍历表达式：
   • 当遇到操作数 1 时，将其入操作数栈。
   • 当遇到操作符 + 时，将其入运算符栈。
   • 当遇到操作数 2 时，将其入操作数栈。
   • 当遇到操作符 * 时，由于其优先级高于栈顶运算符 + ，因此将其入运算符栈。
   • 当遇到操作数 3 时，将其入操作数栈。
   • 当遇到操作符 - 时，由于其优先级小于栈顶运算符 * ，因此先从运算符栈中弹出 * 运算符，再从操作数栈中弹出 2 和 3，进行计算得到 6，并将其入操作数栈，最后将 - 运算符入运算符栈。
   • 当遇到操作数 4 时，将其入操作数栈。
   • 当遇到操作符 / 时，由于其优先级高于栈顶运算符 - ，因此将其入运算符栈。
   • 当遇到操作数 2 时，将其入操作数栈。
3. 遍历结束后，操作数栈中只剩下一个操作数，为最终结果。

因此，中缀表达式 1 + 2 * 3 - 4 / 2 的值为 5。

求解后缀表达式的值

步骤

1. 创建一个栈，用于存储操作数。
2. 从左到右遍历后缀表达式。
3. 如果当前字符是数字，则入操作数栈。
4. 如果当前字符是运算符，则从操作数栈中弹出两个操作数，进行计算后将结果入操作数栈。
5. 重复步骤 3 和 4 直到表达式遍历结束。
6. 从操作数栈中弹出最终结果。

示例

假设我们要求解后缀表达式 1 2 3 * + 4 2 / -。

1. 初始化一个栈：操作数栈。
2. 从左到右遍历表达式：
   • 当遇到操作数 1 时，将其入操作数栈。
   • 当遇到操作数 2 时，将其入操作数栈。
   • 当遇到操作数 3 时，由于其后面紧跟着一个 * 运算符，因此从操作数栈中弹出 2 和 3，进行计算得到 6，并将其入操作数栈。
   • 当遇到操作符 + 时，由于其后面紧跟着一个操作数 4，因此从操作数栈中弹出 1 和 6，进行计算得到 7，并将其入操作数栈。
   • 当遇到操作数 4 时，将其入操作数栈。
   • 当遇到操作数 2 时，由于其后面紧跟着一个 / 运算符，因此从操作数栈中弹出 4 和 2，进行计算得到 2，并将其入操作数栈。
   • 当遇到操作符 - 时，由于其前面已经计算得到了 7 和 2，因此从操作数栈中弹出 2 和 7，进行计算得到 5，并将其入操作数栈。
3. 遍历结束后，操作数栈中只剩下一个操作数，为最终结果。

因此，后缀表达式 1 2 3 * + 4 2 / - 的值为 5。