中缀表达式求值：从理论到实践

引言

中缀表达式，如“3 + 4 * 2”，是我们日常生活中最为熟悉的数学表达式形式。然而，计算机在处理这种表达式时，通常会采用后缀表达式（逆波兰表示法）或前缀表达式，因为它们更易于计算机解析和计算。为了在计算机中处理中缀表达式，我们需要将其转换为后缀表达式，然后进行求值。

中缀表达式到后缀表达式的转换

中缀表达式转换为后缀表达式的算法通常使用栈数据结构来实现。以下是一个简单的算法描述：

1. 初始化一个空的操作栈和一个空的输出列表。
2. 从左到右扫描中缀表达式的每个元素。
3. 如果元素是操作数（如数字或变量），则直接添加到输出列表中。
4. 如果元素是左括号“(”，则将其推入栈。
5. 如果元素是运算符（如“+”、“-”、“*”、“/”），则：
   a. 如果栈不为空，且栈顶的运算符具有与当前运算符相同或更高的优先级，则从栈中弹出并添加到输出列表中。
   b. 将当前运算符推入栈。
6. 如果元素是右括号“)”，则：
   a. 弹出并输出栈顶的运算符，直到看到左括号“(”为止。
   b. 弹出左括号“(”。
7. 当中缀表达式的所有元素都被扫描后，将栈中剩余的所有运算符弹出并添加到输出列表中。

后缀表达式的求值

后缀表达式的求值相对简单，因为不需要考虑运算符的优先级。以下是一个简单的算法描述：

1. 初始化一个空的操作栈。
2. 从左到右扫描后缀表达式的每个元素。
3. 如果元素是操作数，则将其推入栈。
4. 如果元素是运算符，则从栈中弹出相应数量的操作数进行计算，然后将结果推回栈中。
5. 当扫描完后缀表达式的所有元素后，栈中应该只剩下一个元素，即表达式的结果。

实例

假设我们有一个中缀表达式“3 + 4 * 2”。首先，我们将其转换为后缀表达式：

1. 扫描到“3”，输出“3”。
2. 扫描到“+”，压入栈。
3. 扫描到“4”，输出“4”。
4. 扫描到“*”，压入栈。
5. 扫描到“2”，输出“2”。
6. 扫描到“”，从栈中弹出“4”和“2”，计算“4 2 = 8”，将“8”压入栈。
7. 扫描到“+”，从栈中弹出“3”和“8”，计算“3 + 8 = 11”，将“11”压入栈。
8. 扫描结束，栈中只剩下一个元素“11”，即最终结果。

所以，中缀表达式“3 + 4 * 2”的值为“11”。

代码实现

下面是一个简单的Python代码实现，用于将中缀表达式转换为后缀表达式并求值：

```python
def infix_to_postfix(infix):
precedence = {‘+’: 1, ‘-‘: 1, ‘*’: 2, ‘/‘: 2}
output = []
stack = []
for token in infix.split():
if token.isdigit():
output.append(token)
elif token == ‘(‘:
stack.append(token)
elif token == ‘)’:
top_token = stack.pop()
while top_token != ‘(‘:
output.append(top_token)
top_token = stack.pop()
else:
while stack and stack[-1] != ‘(‘ and precedence[stack[-1]] >= precedence[token]:
output.append(stack.pop())
stack.append(token)
while stack:
output.append(stack.pop())
return ‘ ‘.join(output)

def postfix_eval(postfix):
stack = []
for token in postfix.split():
if token.isdigit():
stack.append(int(token))
else:
operand2 = stack.pop()
operand1 = stack.pop()
if token == ‘+’:
result = operand1 + operand2
elif token == ‘-‘: