用Python栈实现中缀表达式求值：从算法原理到工业级代码
在编程竞赛和实际开发中，表达式求值是一个经典问题。很多开发者第一次接触这个问题时，往往会陷入复杂的条件判断和递归调用。但事实上，利用栈这种基础数据结构，配合清晰的算法思路，可以写出既优雅又高效的中缀表达式求值代码。本文将带你用Python实现这一算法，不仅理解其原理，还能掌握工业级代码的编写技巧。
1. 理解表达式求值的核心问题
表达式求值看似简单，实则暗藏玄机。我们日常使用的数学表达式如3 + 5 * 2采用的是中缀表示法，即运算符位于操作数之间。这种表示法对人类友好，但对计算机却不够直观。计算机更擅长处理后缀表达式（也称为逆波兰表示法），如3 5 2 * +，其中运算符跟在操作数之后。
为什么需要转换？中缀表达式需要考虑运算符优先级和括号的影响，而后缀表达式则完全消除了这些复杂性，可以严格按照从左到右的顺序计算。这就是为什么大多数表达式求值算法都采用"中缀转后缀，再计算后缀"的两步走策略。
在Python中，我们可以用列表来模拟栈的行为。栈的LIFO（后进先出）特性完美契合了表达式求值中"最近需要先处理"的场景。例如，当遇到右括号时，我们需要弹出栈中的元素，直到遇到对应的左括号。
2. 中缀转后缀：运算符栈的精妙运用
中缀表达式转后缀表达式是整个过程的核心。我们需要维护一个运算符栈，并按照以下规则处理：
- 初始化一个空栈用于存放运算符，一个空列表用于输出后缀表达式
- 从左到右扫描中缀表达式
- 遇到操作数时，直接加入输出列表
- 遇到运算符时：
- 弹出栈顶优先级不低于当前运算符的所有运算符，加入输出列表
- 然后将当前运算符压入栈中
- 遇到左括号时，直接压入栈中
- 遇到右括号时，弹出栈顶元素加入输出列表，直到遇到左括号（左括号弹出但不输出）
- 表达式扫描完毕后，将栈中剩余运算符全部弹出，加入输出列表
让我们用Python实现这一转换过程：
def infix_to_postfix(expression): precedence = {'+':1, '-':1, '*':2, '/':2, '^':3} stack = [] output = [] for token in expression: if token.isdigit(): output.append(token) elif token == '(': stack.append(token) elif token == ')': while stack and stack[-1] != '(': output.append(stack.pop()) stack.pop() # 弹出左括号但不输出 else: # 运算符 while (stack and stack[-1] != '(' and precedence.get(stack[-1], 0) >= precedence.get(token, 0)): output.append(stack.pop()) stack.append(token) while stack: output.append(stack.pop()) return output这个实现考虑了运算符优先级，但还缺少对多位数和负数的处理。我们将在完整实现中解决这些问题。
3. 后缀表达式求值：操作数栈的简单之美
得到后缀表达式后，求值过程就变得直观多了。我们只需要：
- 初始化一个空栈用于存放操作数
- 从左到右扫描后缀表达式
- 遇到操作数时，压入栈中
- 遇到运算符时，弹出栈顶的两个操作数，进行运算，将结果压回栈中
- 最后栈中剩下的唯一元素就是表达式的结果
Python实现如下：
def evaluate_postfix(postfix): stack = [] for token in postfix: if token.isdigit(): stack.append(int(token)) else: b = stack.pop() a = stack.pop() if token == '+': stack.append(a + b) elif token == '-': stack.append(a - b) elif token == '*': stack.append(a * b) elif token == '/': stack.append(a // b) # 使用整数除法 return stack[0]注意这里我们假设输入已经是合法的后缀表达式。在实际应用中，我们需要先进行表达式验证。
4. 处理边界情况和特殊场景
一个健壮的表达式求值器需要处理各种边界情况：
- 多位数处理：原始算法只能处理单个数字，我们需要改进扫描逻辑
- 负数处理：区分减号和负号是关键
- 空格处理：允许用户输入中包含空格
- 错误处理：检测并报告非法表达式
让我们增强词法分析部分，使其能够处理这些情况：
def tokenize(expression): tokens = [] i = 0 n = len(expression) while i < n: if expression[i] == ' ': i += 1 continue if expression[i] in '+-*/^()': # 处理负号特殊情况 if expression[i] == '-' and (i == 0 or expression[i-1] == '('): tokens.append('NEG') else: tokens.append(expression[i]) i += 1 elif expression[i].isdigit(): num = 0 while i < n and expression[i].isdigit(): num = num * 10 + int(expression[i]) i += 1 tokens.append(str(num)) else: raise ValueError(f"非法字符: {expression[i]}") return tokens对于负号，我们将其标记为特殊的'NEG'运算符，在后续处理中会特别对待。
5. 完整实现与测试
现在我们将所有部分组合起来，创建一个完整的表达式求值器：
class ExpressionEvaluator: def __init__(self): self.precedence = { 'NEG': 4, '^': 3, '*': 2, '/': 2, '+': 1, '-': 1 } def tokenize(self, expression): tokens = [] i = 0 n = len(expression) while i < n: if expression[i] == ' ': i += 1 continue if expression[i] in '+-*/^()': # 处理负号特殊情况 if expression[i] == '-' and (i == 0 or expression[i-1] == '('): tokens.append('NEG') else: tokens.append(expression[i]) i += 1 elif expression[i].isdigit(): num = 0 while i < n and expression[i].isdigit(): num = num * 10 + int(expression[i]) i += 1 tokens.append(str(num)) else: raise ValueError(f"非法字符: {expression[i]}") return tokens def infix_to_postfix(self, tokens): stack = [] output = [] for token in tokens: if token.isdigit(): output.append(token) elif token == '(': stack.append(token) elif token == ')': while stack and stack[-1] != '(': output.append(stack.pop()) stack.pop() # 弹出左括号 else: # 运算符 while (stack and stack[-1] != '(' and self.precedence.get(stack[-1], 0) >= self.precedence.get(token, 0)): output.append(stack.pop()) stack.append(token) while stack: output.append(stack.pop()) return output def evaluate_postfix(self, postfix): stack = [] for token in postfix: if token.isdigit(): stack.append(int(token)) elif token == 'NEG': stack.append(-stack.pop()) else: b = stack.pop() a = stack.pop() if token == '+': stack.append(a + b) elif token == '-': stack.append(a - b) elif token == '*': stack.append(a * b) elif token == '/': stack.append(a // b) elif token == '^': stack.append(a ** b) if len(stack) != 1: raise ValueError("非法表达式") return stack[0] def evaluate(self, expression): tokens = self.tokenize(expression) postfix = self.infix_to_postfix(tokens) return self.evaluate_postfix(postfix) # 使用示例 evaluator = ExpressionEvaluator() print(evaluator.evaluate("3 + 5 * (2 - 8)")) # 输出: -27 print(evaluator.evaluate("-3 + 4 * 2")) # 输出: 5这个实现不仅正确处理了运算符优先级和括号，还能处理负数和空格，是一个相对完整的解决方案。
6. 性能优化与扩展思路
虽然我们的实现已经可以正确处理大多数情况，但在实际应用中还可以进一步优化：
- 表达式验证：在转换前检查括号匹配和运算符位置
- 错误处理：提供更友好的错误信息
- 浮点数支持：扩展词法分析器以支持浮点数
- 变量支持：允许在表达式中使用变量
- 性能优化：使用更高效的数据结构或算法
例如，添加表达式验证的方法：
def validate_expression(self, tokens): paren_stack = [] prev_token = None for token in tokens: if token == '(': paren_stack.append(token) elif token == ')': if not paren_stack: raise ValueError("括号不匹配") paren_stack.pop() # 检查连续两个运算符的情况 if (prev_token in '+-*/^' and token in '+-*/^') and not ( prev_token == ')' and token != '(' or prev_token != ')' and token == '(' ): raise ValueError(f"非法运算符组合: {prev_token}{token}") prev_token = token if paren_stack: raise ValueError("括号不匹配") # 检查首尾运算符 if tokens and tokens[0] in '+-*/^' and tokens[0] != '(': raise ValueError("表达式不能以运算符开头") if tokens and tokens[-1] in '+-*/^' and tokens[-1] != ')': raise ValueError("表达式不能以运算符结尾")在工业级应用中，表达式求值往往需要更复杂的处理。例如，数据库系统中的SQL解析、科学计算软件中的公式处理等，都需要类似的算法作为基础。理解这个核心算法后，你可以轻松扩展到这些更复杂的场景。
