栈在表达式求解中的应用

在计算机科学中，表达式求解是一个基本且重要的任务。栈作为一种先进后出的数据结构，非常适合用于实现算术表达式的求解。本文将首先介绍如何将中缀表达式转换为后缀表达式，然后展示如何使用栈计算后缀表达式。

一、中缀表达式与后缀表达式

中缀表达式是我们日常使用的算术表达式，如 3 + 5 * 2。后缀表达式（也称为逆波兰表示法）则是将运算符放在操作数之后，如 3 5 2 * +。后缀表达式没有括号和运算符优先级的问题，因此更容易被计算机处理。

二、中缀表达式转后缀表达式

要将中缀表达式转换为后缀表达式，我们可以使用两个栈：一个用于存放运算符（opStack），另一个用于存放转换后的后缀表达式（outputStack）。

算法步骤如下：

1. 初始化两个栈 opStack 和 outputStack。
2. 从左到右扫描中缀表达式的每个字符。
3. 如果字符是操作数，直接将其压入 outputStack。
4. 如果字符是左括号 (，将其压入 opStack。
5. 如果字符是右括号 )，则从 opStack 中弹出并输出所有运算符，直到遇到左括号 ( 为止（左括号只弹出不输出）。
6. 如果字符是运算符（如 +、-、*、/），则：
   a. 如果 opStack 不为空，且栈顶运算符具有与当前运算符相同或更高的优先级，则从 opStack 弹出并压入 outputStack。
   b. 将当前运算符压入 opStack。
7. 当中缀表达式扫描结束后，将 opStack 中剩余的运算符依次弹出并压入 outputStack。

三、后缀表达式的计算

计算后缀表达式时，我们只需要一个栈（operandStack）即可。从左到右扫描后缀表达式的每个字符，如果字符是操作数，则直接压入 operandStack；如果字符是运算符，则从 operandStack 中弹出相应数量的操作数进行计算，并将结果压回 operandStack。

四、实例演示

以中缀表达式 3 + 5 * 2 为例，转换为后缀表达式为 3 5 2 * +。

计算后缀表达式的过程如下：

1. 扫描到 3，压入 operandStack。
2. 扫描到 5，压入 operandStack。
3. 扫描到 2，压入 operandStack。
4. 扫描到 *，从 operandStack 弹出 2 和 5，计算 5 * 2 = 10，将结果 10 压入 operandStack。
5. 扫描到 +，从 operandStack 弹出 10 和 3，计算 10 + 3 = 13，将结果 13 压入 operandStack。
6. 扫描结束，从 operandStack 弹出最终结果 13，即为表达式 3 + 5 * 2 的值。

五、代码实现

下面是一个使用 Python 实现的简单例子：

```python
def infix_to_postfix(expression):
opStack = []
output = []
precedence = {‘+’: 1, ‘-‘: 1, ‘*’: 2, ‘/‘: 2}

for char in expression:
    if char.isdigit():
        output.append(char)
    elif char == '(':
        opStack.append(char)
    elif char == ')':
        topToken = opStack.pop()
        while topToken != '(':
            output.append(topToken)
            topToken = opStack.pop()
    else:
        while opStack and precedence[opStack[-1]] >= precedence[char]:
            output.append(opStack.pop())
        opStack.append(char)
while opStack:
    output.append(opStack.pop())
return ''.join(output)

def postfix_eval(expression):
operandStack = []
precedence = {‘+’: 1, ‘-‘: 1, ‘*’: 2, ‘/‘: 2}

for char