本文将介绍如何使用 Python 实现后缀表达式（也称为逆波兰表达式）的解析和求值。我们将首先实现一个简单的词法分析器（tokenizer），然后构建一个递归下降解析器（recursive descent parser）来将标记流转换为抽象语法树（AST），最后实现一个求值器来计算表达式的结果。
理解后缀表达式
后缀表达式是一种不需要括号来表示运算优先级的算术表达式。在后缀表达式中，操作符位于操作数之后。例如，中缀表达式 2 + 3 * 4 的后缀表达式形式为 2 3 4 * +。
实现词法分析器（Tokenizer）
词法分析器负责将输入的字符串分解成一个个的标记（token）。对于后缀表达式，我们需要识别数字和操作符。
import re
token_patterns = [
('OPERATOR', r'[+\-*/]'),
('NUMBER', r'\d+'),
('WHITESPACE', r'\s+'),
]
def tokenize(source_code):
tokens = []
source_code = source_code.strip()
while source_code:
matched = False
for token_type, pattern in token_patterns:
match = re.match(pattern, source_code)
if match:
value = match.group(0)
tokens.append((token_type, value))
source_code = source_code[len(value):].lstrip()
matched = True
break
if not matched:
raise ValueError(f"Invalid character in source code: {source_code[0]}")
return tokens这段代码定义了一个 tokenize 函数，它接收一个字符串作为输入，并返回一个包含标记的列表。每个标记是一个元组，包含标记的类型和值。正则表达式用于匹配数字、操作符和空白字符。
立即学习“Python免费学习笔记（深入）”；
实现解析器（Parser）
解析器负责将标记流转换为抽象语法树（AST）。对于后缀表达式，AST 可以表示为一个嵌套的元组结构。
原始代码的问题在于解析器的逻辑错误。在后缀表达式中，操作符应该在两个操作数之后。因此，解析器的逻辑应该调整为先解析两个操作数，然后解析操作符。
def parse_expression(tokens):
stack = []
for token_type, value in tokens:
if token_type == 'NUMBER':
stack.append(int(value))
elif token_type == 'OPERATOR':
if len(stack) < 2:
raise ValueError("Not enough operands for operator: {}".format(value))
right = stack.pop()
left = stack.pop()
stack.append((value, left, right))
else:
raise ValueError(f"Unexpected token: {token_type}")
if len(stack) != 1:
raise ValueError("Invalid expression")
return stack.pop()这段代码使用一个栈来存储操作数和中间结果。当遇到数字时，将其压入栈中。当遇到操作符时，从栈中弹出两个操作数，然后将操作符和操作数组成一个元组，再将结果压入栈中。
实现求值器（Evaluator）
求值器负责计算抽象语法树的结果。
def evaluate_expression(expression):
if isinstance(expression, int):
return expression
elif isinstance(expression, tuple):
operator, left, right = expression
if operator == '+':
return evaluate_expression(left) + evaluate_expression(right)
elif operator == '-':
return evaluate_expression(left) - evaluate_expression(right)
elif operator == '*':
return evaluate_expression(left) * evaluate_expression(right)
elif operator == '/':
return evaluate_expression(left) / evaluate_expression(right)
else:
raise ValueError(f"Invalid expression: {expression}")这段代码递归地计算表达式的结果。如果表达式是一个数字，则直接返回该数字。如果表达式是一个元组，则递归地计算操作数的结果，然后根据操作符执行相应的运算。
完整代码示例
import re
token_patterns = [
('OPERATOR', r'[+\-*/]'),
('NUMBER', r'\d+'),
('WHITESPACE', r'\s+'),
]
def tokenize(source_code):
tokens = []
source_code = source_code.strip()
while source_code:
matched = False
for token_type, pattern in token_patterns:
match = re.match(pattern, source_code)
if match:
value = match.group(0)
tokens.append((token_type, value))
source_code = source_code[len(value):].lstrip()
matched = True
break
if not matched:
raise ValueError(f"Invalid character in source code: {source_code[0]}")
return tokens
def parse_expression(tokens):
stack = []
for token_type, value in tokens:
if token_type == 'NUMBER':
stack.append(int(value))
elif token_type == 'OPERATOR':
if len(stack) < 2:
raise ValueError("Not enough operands for operator: {}".format(value))
right = stack.pop()
left = stack.pop()
stack.append((value, left, right))
else:
raise ValueError(f"Unexpected token: {token_type}")
if len(stack) != 1:
raise ValueError("Invalid expression")
return stack.pop()
def evaluate_expression(expression):
if isinstance(expression, int):
return expression
elif isinstance(expression, tuple):
operator, left, right = expression
if operator == '+':
return evaluate_expression(left) + evaluate_expression(right)
elif operator == '-':
return evaluate_expression(left) - evaluate_expression(right)
elif operator == '*':
return evaluate_expression(left) * evaluate_expression(right)
elif operator == '/':
return evaluate_expression(left) / evaluate_expression(right)
else:
raise ValueError(f"Invalid expression: {expression}")
def main():
source_code = "2 3 4 * +"
tokens = tokenize(source_code)
parsed_expression = parse_expression(tokens)
print(f"Source code: {source_code}")
print(f"Parsed expression: {parsed_expression}")
result = evaluate_expression(parsed_expression)
print(f"Result: {result}")
if __name__ == "__main__":
main()这段代码将输出：
Source code: 2 3 4 * +
Parsed expression: ('+', 2, ('*', 3, 4))
Result: 14总结
本文介绍了如何使用 Python 实现后缀表达式的解析和求值。通过实现一个简单的词法分析器、解析器和求值器，我们了解了后缀表达式的基本概念、解析过程以及如何使用 Python 实现一个简单的后缀表达式计算器。这个例子展示了递归下降解析器的基本原理，并提供了一个可扩展的基础，可以用于构建更复杂的解析器。
