如何使用 python 写一个简单的表达式解释器？
好了，咱们今天不谈那些虚头巴脑的“人工智能”、“机器学习”，就来聊点实在的——怎么用 Python 写一个能懂数学算式的“翻译官”，也就是一个简单的表达式解释器。这就像是教一个不懂数学的小朋友认字一样，我们得一步步来，让他理解加减乘除这些基本操作。
这篇文章我尽量说得详细点，像老朋友聊天一样，把那些晦涩的概念都掰开了揉碎了讲。目标是写完这篇，你不仅能看懂我的思路，还能自己动手写出一个能算简单算式的 Python 程序。
为啥要写个表达式解释器？
你可能会问，Python 本身就能算啊，`2 + 3 5` 直接就能出结果。为啥还要费劲巴拉地自己写一个？
原因有很多。首先，这是一个很好的学习过程。理解一个程序是怎么把一串字符变成一个计算结果，就像剥洋葱一样，一层层地揭开它的运作机制。其次，我们自己写的解释器，在功能上可以更灵活。比如，你想让它支持变量、函数，甚至自定义的运算符号，用 Python 原生的 `eval()` 是做不到的，或者说做起来很麻烦且有安全隐患。
所以，咱们就把它当成一次“编程探险”吧，看看怎么把用户输入的“2 + 3 5”变成电脑能懂的“计算过程”。
核心思路：把算式“翻译”成电脑能懂的语言
想象一下，你拿到一张写满算式的纸条：“3 + 4 (2 1)”。你要怎么计算？
你不会傻乎乎地从左往右直接算。你会先看括号里面的，然后是乘除，最后是加减。这背后其实有一套规则，叫做运算符优先级。我们写解释器，就是要模拟这个“计算大脑”。
将一串字符串算式转化为计算机可执行的指令（或者更准确地说，是转化为一种计算机容易理解的数据结构），这通常分成几个关键步骤：
1. 词法分析 (Lexing / Tokenizing): 把原始的字符串算式，“拆解”成一个个有意义的“单词”，我们称之为“记号”（Token）。就像把一句话拆分成词语一样。
2. 语法分析 (Parsing): 根据一套预先定义的“语法规则”，把这些记号组织起来，形成一个有结构的信息，通常是一个“抽象语法树”（Abstract Syntax Tree, AST）。这就像把词语组合成句子，并且明白句子的主谓宾结构。
3. 求值 (Evaluation): 遍历这个抽象语法树，按照树的结构和节点代表的运算，一步步地算出最终结果。
咱们就按这个顺序一步步来。
第一步：词法分析——拆解算式
我们先来处理“词法分析”这个环节。我们的目标是把像 `"3 + 4 (2 1)"` 这样的字符串，变成一系列的记号。
记号是什么？它可以是：
数字 (Number): 比如 `3`, `4`, `2`, `1`
运算符 (Operator): 比如 `+`, ``, ``, `/`
括号 (Parenthesis): 比如 `(`, `)`
空白符 (Whitespace): 比如空格，我们通常会忽略它们。
我们来定义一个函数，叫做 `tokenize`，它接收一个字符串算式，返回一个记号列表。
首先，我们需要一个 `Token` 类来表示记号。一个记号应该包含它的类型（比如是数字、加号还是左括号）和它的值（比如数字是 3，运算符是 '+'）。
```python
class Token:
def __init__(self, type, value):
self.type = type
self.value = value
def __repr__(self):
return f"Token({self.type}, {self.value})"
定义一些记号类型
INTEGER = 'INTEGER'
PLUS = 'PLUS'
MINUS = 'MINUS'
MULTIPLY = 'MULTIPLY'
DIVIDE = 'DIVIDE'
LPAREN = 'LPAREN'
RPAREN = 'RPAREN'
EOF = 'EOF' End Of File, 表示输入结束
```
现在，我们来实现 `tokenize` 函数。这个函数需要遍历输入的字符串，识别出不同的记号。
我们可以用一个指针（或者说一个索引 `pos`）来标记当前在字符串的哪个位置。
```python
def tokenize(text):
tokens = []
pos = 0
text_len = len(text)
while pos < text_len:
char = text[pos]
1. 跳过空白符
if char.isspace():
pos += 1
continue
2. 识别数字
if char.isdigit():
num_str = ""
while pos < text_len and text[pos].isdigit():
num_str += text[pos]
pos += 1
tokens.append(Token(INTEGER, int(num_str)))
continue 继续下一次循环，因为pos已经前进过了
3. 识别运算符和括号
if char == '+':
tokens.append(Token(PLUS, '+'))
pos += 1
elif char == '':
tokens.append(Token(MINUS, ''))
pos += 1
elif char == '':
tokens.append(Token(MULTIPLY, ''))
pos += 1
elif char == '/':
tokens.append(Token(DIVIDE, '/'))
pos += 1
elif char == '(':
tokens.append(Token(LPAREN, '('))
pos += 1
elif char == ')':
tokens.append(Token(RPAREN, ')'))
pos += 1
else:
如果遇到不认识的字符，抛出错误
raise ValueError(f"Unexpected character: {char}")
在最后添加一个EOF记号，表示输入结束
tokens.append(Token(EOF, None))
return tokens
```
咱们来测试一下：
```python
expression = "3 + 4 (2 1)"
tokens = tokenize(expression)
print(tokens)
```
输出应该会是类似这样的列表：
```
[Token(INTEGER, 3), Token(PLUS, '+'), Token(INTEGER, 4), Token(MULTIPLY, ''), Token(LPAREN, '('), Token(INTEGER, 2), Token(MINUS, ''), Token(INTEGER, 1), Token(RPAREN, ')'), Token(EOF, None)]
```
看起来不错，我们成功地把字符串拆解成了一个个有意义的小单元。
第二步：语法分析——构建“抽象语法树”
有了记号列表，我们接下来需要把它们组织起来，形成一个有结构的表示。就像把词语组成一个有逻辑的句子。这个结构通常用“抽象语法树”（AST）来表示。
为什么是树？因为算式本身就有层级关系。比如 `3 + 4 2`，乘法 `4 2` 是一个子运算，它的结果再和 `3` 相加。这天然就是一个树形结构。
叶子节点通常是数字。
内部节点是运算符，它们有子节点，代表参与运算的数或子表达式。
例如，表达式 `3 + 4 2` 的 AST 可能看起来像这样：
```
+
/
3
/
4 2
```
要构建 AST，我们需要一个“解析器”（Parser）。解析器会“消费”我们生成的记号列表，并根据一套语法规则来生成树。
对于算术表达式，一个常见的解析技术是“递归下降解析”（Recursive Descent Parsing）。这种方法很简单，就是根据算式的结构，定义一系列函数，每个函数负责解析算式的一部分。
我们先来定义表示 AST 节点的类。
```python
AST节点类型
class AST:
pass
class BinOp(AST): Binary Operation (二元运算)
def __init__(self, left, op, right):
self.left = left
self.op = op 运算符记号
self.right = right
class Num(AST): Number (数字)
def __init__(self, token):
self.token = token
self.value = token.value
class Parser:
def __init__(self, tokens):
self.tokens = tokens
self.token_idx = 0
self.current_token = self.tokens[self.token_idx]
def error(self, message="Invalid syntax"):
raise Exception(f"Parser error: {message}")
def eat(self, token_type):
消费当前记号，如果类型匹配的话
if self.current_token.type == token_type:
self.token_idx += 1
if self.token_idx < len(self.tokens):
self.current_token = self.tokens[self.token_idx]
else:
当没有更多记号时，current_token 可以设为一个特殊的EOF标记，
但这里我们直接用最后一个记号的类型来判断是否结束
pass
else:
self.error(f"Expected {token_type}, but got {self.current_token.type}")
def factor(self):
"""解析因子 (factor)，可以是数字，或者带括号的表达式"""
token = self.current_token
if token.type == INTEGER:
self.eat(INTEGER)
return Num(token)
elif token.type == LPAREN:
self.eat(LPAREN)
node = self.expr() 解析括号内的表达式
self.eat(RPAREN)
return node
else:
self.error("Expected integer or parenthesis")
def term(self):
"""解析项 (term)，包含乘除运算"""
node = self.factor() 先解析一个因子
while self.current_token.type in (MULTIPLY, DIVIDE):
op_token = self.current_token
if op_token.type == MULTIPLY:
self.eat(MULTIPLY)
elif op_token.type == DIVIDE:
self.eat(DIVIDE)
right_node = self.factor() 解析乘除号右边的因子
node = BinOp(left=node, op=op_token, right=right_node)
return node
def expr(self):
"""解析表达式 (expr)，包含加减运算"""
node = self.term() 先解析一个项
while self.current_token.type in (PLUS, MINUS):
op_token = self.current_token
if op_token.type == PLUS:
self.eat(PLUS)
elif op_token.type == MINUS:
self.eat(MINUS)
right_node = self.term() 解析加减号右边的项
node = BinOp(left=node, op=op_token, right=right_node)
return node
def parse(self):
"""入口方法，开始解析"""
ast_tree = self.expr()
确保所有记号都被消费了，除了EOF
if self.current_token.type != EOF:
self.error("Not all tokens consumed")
return ast_tree
```
这里我们定义了处理运算符优先级的规则：
`factor`: 处理最基本的部分，也就是数字和括号内的表达式。
`term`: 处理乘法和除法。它会先解析一个 `factor`，然后循环检查后面是否跟着乘除号，如果是，就继续解析下一个 `factor`，并将它们组合成 `BinOp` 节点。
`expr`: 处理加法和减法。它会先解析一个 `term`，然后循环检查后面是否跟着加减号，如果是，就继续解析下一个 `term`，并将它们组合成 `BinOp` 节点。
这种结构自然地实现了运算符的优先级：乘除法（`term`）先于加减法（`expr`）被处理。括号通过 `factor` 中的递归调用 `self.expr()` 来实现。
咱们来测试一下：
```python
expression = "3 + 4 2 1"
tokens = tokenize(expression)
parser = Parser(tokens)
ast_tree = parser.parse()
为了方便查看，我们可以写一个打印AST的函数（这部分不是必须的，但有助于理解）
def print_ast(node, indent=0):
prefix = " " indent
if isinstance(node, Num):
print(f"{prefix}Num({node.value})")
elif isinstance(node, BinOp):
print(f"{prefix}BinOp({node.op.value})")
print_ast(node.left, indent + 1)
print_ast(node.right, indent + 1)
else:
print(f"{prefix}{node}")
print_ast(ast_tree)
```
对于 `"3 + 4 2 1"`，预期的 AST 结构大致是：
```
BinOp(+)
Num(3)
BinOp()
Num(4)
Num(2)
Num(1)
```
输出可能看起来是这样的：
```
BinOp(+)
Num(3)
BinOp()
Num(4)
Num(2)
Num(1)
```
这里有一个小问题，因为 `term` 是从左往右处理乘除的，`expr` 也是从左往右处理加减的。所以对于 `3 4 + 5`，它会先计算 `3 4`，再加 `5`。对于 `10 / 2 5`，它会先计算 `10 / 2`，再乘 `5`。这符合我们通常的数学习惯。
第三步：求值——让树动起来
现在我们有了数据结构（AST），接下来就是执行它，算出最终结果。这个过程叫做“求值”（Evaluation）。
我们可以创建一个 `Interpreter`（解释器）类，它的任务就是遍历 AST，执行其中的运算。
```python
class Interpreter:
def __init__(self, parser):
self.parser = parser
def visit(self, node):
"""根据节点类型，调用相应的访问方法"""
method_name = 'visit_' + type(node).__name__
visitor = getattr(self, method_name, self.generic_visit)
return visitor(node)
def generic_visit(self, node):
"""默认的访问方法，如果找不到特定的访问方法的话"""
raise Exception(f'No visit_{type(node).__name__} method')
def visit_BinOp(self, node):
"""访问二元运算节点"""
if node.op.type == PLUS:
return self.visit(node.left) + self.visit(node.right)
elif node.op.type == MINUS:
return self.visit(node.left) self.visit(node.right)
elif node.op.type == MULTIPLY:
return self.visit(node.left) self.visit(node.right)
elif node.op.type == DIVIDE:
注意：这里我们做的是整除，如果需要浮点除，可以用 float(self.visit(node.left)) / self.visit(node.right)
return self.visit(node.left) // self.visit(node.right)
else:
raise ValueError(f"Unknown operator: {node.op.type}")
def visit_Num(self, node):
"""访问数字节点"""
return node.value
def interpret(self):
"""开始解释，计算最终结果"""
tree = self.parser.parse()
return self.visit(tree)
```
`visit` 方法是一个通用的入口，它会根据当前节点的具体类型（`Num` 或 `BinOp`）找到对应的 `visit_Num` 或 `visit_BinOp` 方法来执行。这是一种常见的访问者模式（Visitor Pattern）的应用，让代码结构更清晰。
现在，我们可以把它们串起来：
```python
def evaluate(expression):
tokens = tokenize(expression)
parser = Parser(tokens)
interpreter = Interpreter(parser)
return interpreter.interpret()
测试一下
expression1 = "3 + 4 2 1"
result1 = evaluate(expression1)
print(f"'{expression1}' = {result1}") 预期输出: '3 + 4 2 1' = 10
expression2 = "7 (2 + 3) 5"
result2 = evaluate(expression2)
print(f"'{expression2}' = {result2}") 预期输出: '7 (2 + 3) 5' = 30
expression3 = "10 / 2 + 5 3"
result3 = evaluate(expression3)
print(f"'{expression3}' = {result3}") 预期输出: '10 / 2 + 5 3' = 20
```
整个流程的总结与回顾
我们一步步地构建了一个简单的表达式解释器。让我们回顾一下这个过程：
1. 词法分析 (Lexing):
将原始的字符串算式（如 `"3 + 4 (2 1)"`）分解成一个个有意义的“记号”（Tokens），例如 `[Token(INTEGER, 3), Token(PLUS, '+'), Token(INTEGER, 4), Token(MULTIPLY, ''), ...]`。
我们定义了 `Token` 类来表示这些记号的类型和值。
`tokenize` 函数负责这个过程。
2. 语法分析 (Parsing):
根据预定义的语法规则（运算符优先级、括号匹配等），将记号列表组织成一个结构化的表示——抽象语法树（AST）。
`AST` 类作为基类，`Num` 和 `BinOp` 是具体的节点类型。
`Parser` 类实现了递归下降解析，通过 `factor`, `term`, `expr` 方法来处理不同的优先级和结构。
3. 求值 (Evaluation):
遍历 AST，根据节点代表的运算执行实际的计算。
`Interpreter` 类使用访问者模式 (`visit` 方法) 来处理不同类型的节点。
`visit_BinOp` 执行运算，`visit_Num` 返回数字本身。
整个过程就像我们人类计算数学题一样：先看懂算式里都有啥（词法分析），再弄清楚先算哪一部分，后算哪一部分（语法分析），最后一步一步地算出结果（求值）。
还可以往哪儿发展？
这个解释器虽然简单，但已经展示了核心原理。要让它更强大，还可以做很多事情：
浮点数支持: 修改 `tokenize` 和 `visit_Num` 来处理 `1.5` 这样的数字，以及在除法时使用浮点运算。
变量: 引入 `IDENTIFIER` 记号类型，并在 `Interpreter` 中维护一个变量字典。`visit_Identifier` 方法会从字典中查找变量值。
函数调用: 比如 `sin(3.14)`。这需要新的记号类型，以及在 AST 中表示函数调用的节点类型，并在 `Interpreter` 中实现函数调用逻辑（可能需要一个函数查找表）。
一元运算符: 例如 `5`。这需要修改 `factor` 函数来处理前导的 `` 号。
更多运算符: 比如取模 `%`，幂 `` 等。
错误处理: 目前的错误处理比较粗糙，可以做得更精细，给出更友好的错误信息。
写在最后
希望这番“唠叨”能让你对如何写一个简单的表达式解释器有个清晰的认识。从字符串到抽象的计算结构，再到最终的结果，这中间的每一步都充满了编程的智慧。
写完这些代码，你是不是感觉自己像一个“数字世界的翻译家”？从人类能理解的语言，翻译成计算机能执行的指令。这正是编程的魅力所在。
如果你有兴趣，不妨试试给它加点新功能，让它变得更强大、更智能。祝你编程愉快！
这篇文章我尽量说得详细点，像老朋友聊天一样，把那些晦涩的概念都掰开了揉碎了讲。目标是写完这篇，你不仅能看懂我的思路，还能自己动手写出一个能算简单算式的 Python 程序。
为啥要写个表达式解释器？
你可能会问，Python 本身就能算啊，`2 + 3 5` 直接就能出结果。为啥还要费劲巴拉地自己写一个？
原因有很多。首先，这是一个很好的学习过程。理解一个程序是怎么把一串字符变成一个计算结果，就像剥洋葱一样，一层层地揭开它的运作机制。其次，我们自己写的解释器，在功能上可以更灵活。比如，你想让它支持变量、函数，甚至自定义的运算符号，用 Python 原生的 `eval()` 是做不到的，或者说做起来很麻烦且有安全隐患。
所以，咱们就把它当成一次“编程探险”吧，看看怎么把用户输入的“2 + 3 5”变成电脑能懂的“计算过程”。
核心思路：把算式“翻译”成电脑能懂的语言
想象一下，你拿到一张写满算式的纸条：“3 + 4 (2 1)”。你要怎么计算？
你不会傻乎乎地从左往右直接算。你会先看括号里面的，然后是乘除，最后是加减。这背后其实有一套规则，叫做运算符优先级。我们写解释器，就是要模拟这个“计算大脑”。
将一串字符串算式转化为计算机可执行的指令（或者更准确地说，是转化为一种计算机容易理解的数据结构），这通常分成几个关键步骤：
1. 词法分析 (Lexing / Tokenizing): 把原始的字符串算式，“拆解”成一个个有意义的“单词”，我们称之为“记号”（Token）。就像把一句话拆分成词语一样。
2. 语法分析 (Parsing): 根据一套预先定义的“语法规则”，把这些记号组织起来，形成一个有结构的信息，通常是一个“抽象语法树”（Abstract Syntax Tree, AST）。这就像把词语组合成句子，并且明白句子的主谓宾结构。
3. 求值 (Evaluation): 遍历这个抽象语法树，按照树的结构和节点代表的运算，一步步地算出最终结果。
咱们就按这个顺序一步步来。
第一步：词法分析——拆解算式
我们先来处理“词法分析”这个环节。我们的目标是把像 `"3 + 4 (2 1)"` 这样的字符串，变成一系列的记号。
记号是什么？它可以是：
数字 (Number): 比如 `3`, `4`, `2`, `1`
运算符 (Operator): 比如 `+`, ``, ``, `/`
括号 (Parenthesis): 比如 `(`, `)`
空白符 (Whitespace): 比如空格，我们通常会忽略它们。
我们来定义一个函数，叫做 `tokenize`，它接收一个字符串算式，返回一个记号列表。
首先，我们需要一个 `Token` 类来表示记号。一个记号应该包含它的类型（比如是数字、加号还是左括号）和它的值（比如数字是 3，运算符是 '+'）。
```python
class Token:
def __init__(self, type, value):
self.type = type
self.value = value
def __repr__(self):
return f"Token({self.type}, {self.value})"
定义一些记号类型
INTEGER = 'INTEGER'
PLUS = 'PLUS'
MINUS = 'MINUS'
MULTIPLY = 'MULTIPLY'
DIVIDE = 'DIVIDE'
LPAREN = 'LPAREN'
RPAREN = 'RPAREN'
EOF = 'EOF' End Of File, 表示输入结束
```
现在，我们来实现 `tokenize` 函数。这个函数需要遍历输入的字符串，识别出不同的记号。
我们可以用一个指针（或者说一个索引 `pos`）来标记当前在字符串的哪个位置。
```python
def tokenize(text):
tokens = []
pos = 0
text_len = len(text)
while pos < text_len:
char = text[pos]
1. 跳过空白符
if char.isspace():
pos += 1
continue
2. 识别数字
if char.isdigit():
num_str = ""
while pos < text_len and text[pos].isdigit():
num_str += text[pos]
pos += 1
tokens.append(Token(INTEGER, int(num_str)))
continue 继续下一次循环，因为pos已经前进过了
3. 识别运算符和括号
if char == '+':
tokens.append(Token(PLUS, '+'))
pos += 1
elif char == '':
tokens.append(Token(MINUS, ''))
pos += 1
elif char == '':
tokens.append(Token(MULTIPLY, ''))
pos += 1
elif char == '/':
tokens.append(Token(DIVIDE, '/'))
pos += 1
elif char == '(':
tokens.append(Token(LPAREN, '('))
pos += 1
elif char == ')':
tokens.append(Token(RPAREN, ')'))
pos += 1
else:
如果遇到不认识的字符，抛出错误
raise ValueError(f"Unexpected character: {char}")
在最后添加一个EOF记号，表示输入结束
tokens.append(Token(EOF, None))
return tokens
```
咱们来测试一下：
```python
expression = "3 + 4 (2 1)"
tokens = tokenize(expression)
print(tokens)
```
输出应该会是类似这样的列表：
```
[Token(INTEGER, 3), Token(PLUS, '+'), Token(INTEGER, 4), Token(MULTIPLY, ''), Token(LPAREN, '('), Token(INTEGER, 2), Token(MINUS, ''), Token(INTEGER, 1), Token(RPAREN, ')'), Token(EOF, None)]
```
看起来不错，我们成功地把字符串拆解成了一个个有意义的小单元。
第二步：语法分析——构建“抽象语法树”
有了记号列表，我们接下来需要把它们组织起来，形成一个有结构的表示。就像把词语组成一个有逻辑的句子。这个结构通常用“抽象语法树”（AST）来表示。
为什么是树？因为算式本身就有层级关系。比如 `3 + 4 2`，乘法 `4 2` 是一个子运算，它的结果再和 `3` 相加。这天然就是一个树形结构。
叶子节点通常是数字。
内部节点是运算符，它们有子节点，代表参与运算的数或子表达式。
例如，表达式 `3 + 4 2` 的 AST 可能看起来像这样：
```
+
/
3
/
4 2
```
要构建 AST，我们需要一个“解析器”（Parser）。解析器会“消费”我们生成的记号列表，并根据一套语法规则来生成树。
对于算术表达式，一个常见的解析技术是“递归下降解析”（Recursive Descent Parsing）。这种方法很简单，就是根据算式的结构，定义一系列函数，每个函数负责解析算式的一部分。
我们先来定义表示 AST 节点的类。
```python
AST节点类型
class AST:
pass
class BinOp(AST): Binary Operation (二元运算)
def __init__(self, left, op, right):
self.left = left
self.op = op 运算符记号
self.right = right
class Num(AST): Number (数字)
def __init__(self, token):
self.token = token
self.value = token.value
class Parser:
def __init__(self, tokens):
self.tokens = tokens
self.token_idx = 0
self.current_token = self.tokens[self.token_idx]
def error(self, message="Invalid syntax"):
raise Exception(f"Parser error: {message}")
def eat(self, token_type):
消费当前记号，如果类型匹配的话
if self.current_token.type == token_type:
self.token_idx += 1
if self.token_idx < len(self.tokens):
self.current_token = self.tokens[self.token_idx]
else:
当没有更多记号时，current_token 可以设为一个特殊的EOF标记，
但这里我们直接用最后一个记号的类型来判断是否结束
pass
else:
self.error(f"Expected {token_type}, but got {self.current_token.type}")
def factor(self):
"""解析因子 (factor)，可以是数字，或者带括号的表达式"""
token = self.current_token
if token.type == INTEGER:
self.eat(INTEGER)
return Num(token)
elif token.type == LPAREN:
self.eat(LPAREN)
node = self.expr() 解析括号内的表达式
self.eat(RPAREN)
return node
else:
self.error("Expected integer or parenthesis")
def term(self):
"""解析项 (term)，包含乘除运算"""
node = self.factor() 先解析一个因子
while self.current_token.type in (MULTIPLY, DIVIDE):
op_token = self.current_token
if op_token.type == MULTIPLY:
self.eat(MULTIPLY)
elif op_token.type == DIVIDE:
self.eat(DIVIDE)
right_node = self.factor() 解析乘除号右边的因子
node = BinOp(left=node, op=op_token, right=right_node)
return node
def expr(self):
"""解析表达式 (expr)，包含加减运算"""
node = self.term() 先解析一个项
while self.current_token.type in (PLUS, MINUS):
op_token = self.current_token
if op_token.type == PLUS:
self.eat(PLUS)
elif op_token.type == MINUS:
self.eat(MINUS)
right_node = self.term() 解析加减号右边的项
node = BinOp(left=node, op=op_token, right=right_node)
return node
def parse(self):
"""入口方法，开始解析"""
ast_tree = self.expr()
确保所有记号都被消费了，除了EOF
if self.current_token.type != EOF:
self.error("Not all tokens consumed")
return ast_tree
```
这里我们定义了处理运算符优先级的规则：
`factor`: 处理最基本的部分，也就是数字和括号内的表达式。
`term`: 处理乘法和除法。它会先解析一个 `factor`，然后循环检查后面是否跟着乘除号，如果是，就继续解析下一个 `factor`，并将它们组合成 `BinOp` 节点。
`expr`: 处理加法和减法。它会先解析一个 `term`，然后循环检查后面是否跟着加减号，如果是，就继续解析下一个 `term`，并将它们组合成 `BinOp` 节点。
这种结构自然地实现了运算符的优先级：乘除法（`term`）先于加减法（`expr`）被处理。括号通过 `factor` 中的递归调用 `self.expr()` 来实现。
咱们来测试一下：
```python
expression = "3 + 4 2 1"
tokens = tokenize(expression)
parser = Parser(tokens)
ast_tree = parser.parse()
为了方便查看，我们可以写一个打印AST的函数（这部分不是必须的，但有助于理解）
def print_ast(node, indent=0):
prefix = " " indent
if isinstance(node, Num):
print(f"{prefix}Num({node.value})")
elif isinstance(node, BinOp):
print(f"{prefix}BinOp({node.op.value})")
print_ast(node.left, indent + 1)
print_ast(node.right, indent + 1)
else:
print(f"{prefix}{node}")
print_ast(ast_tree)
```
对于 `"3 + 4 2 1"`，预期的 AST 结构大致是：
```
BinOp(+)
Num(3)
BinOp()
Num(4)
Num(2)
Num(1)
```
输出可能看起来是这样的：
```
BinOp(+)
Num(3)
BinOp()
Num(4)
Num(2)
Num(1)
```
这里有一个小问题，因为 `term` 是从左往右处理乘除的，`expr` 也是从左往右处理加减的。所以对于 `3 4 + 5`，它会先计算 `3 4`，再加 `5`。对于 `10 / 2 5`，它会先计算 `10 / 2`，再乘 `5`。这符合我们通常的数学习惯。
第三步：求值——让树动起来
现在我们有了数据结构（AST），接下来就是执行它，算出最终结果。这个过程叫做“求值”（Evaluation）。
我们可以创建一个 `Interpreter`（解释器）类，它的任务就是遍历 AST，执行其中的运算。
```python
class Interpreter:
def __init__(self, parser):
self.parser = parser
def visit(self, node):
"""根据节点类型，调用相应的访问方法"""
method_name = 'visit_' + type(node).__name__
visitor = getattr(self, method_name, self.generic_visit)
return visitor(node)
def generic_visit(self, node):
"""默认的访问方法，如果找不到特定的访问方法的话"""
raise Exception(f'No visit_{type(node).__name__} method')
def visit_BinOp(self, node):
"""访问二元运算节点"""
if node.op.type == PLUS:
return self.visit(node.left) + self.visit(node.right)
elif node.op.type == MINUS:
return self.visit(node.left) self.visit(node.right)
elif node.op.type == MULTIPLY:
return self.visit(node.left) self.visit(node.right)
elif node.op.type == DIVIDE:
注意：这里我们做的是整除，如果需要浮点除，可以用 float(self.visit(node.left)) / self.visit(node.right)
return self.visit(node.left) // self.visit(node.right)
else:
raise ValueError(f"Unknown operator: {node.op.type}")
def visit_Num(self, node):
"""访问数字节点"""
return node.value
def interpret(self):
"""开始解释，计算最终结果"""
tree = self.parser.parse()
return self.visit(tree)
```
`visit` 方法是一个通用的入口，它会根据当前节点的具体类型（`Num` 或 `BinOp`）找到对应的 `visit_Num` 或 `visit_BinOp` 方法来执行。这是一种常见的访问者模式（Visitor Pattern）的应用，让代码结构更清晰。
现在，我们可以把它们串起来：
```python
def evaluate(expression):
tokens = tokenize(expression)
parser = Parser(tokens)
interpreter = Interpreter(parser)
return interpreter.interpret()
测试一下
expression1 = "3 + 4 2 1"
result1 = evaluate(expression1)
print(f"'{expression1}' = {result1}") 预期输出: '3 + 4 2 1' = 10
expression2 = "7 (2 + 3) 5"
result2 = evaluate(expression2)
print(f"'{expression2}' = {result2}") 预期输出: '7 (2 + 3) 5' = 30
expression3 = "10 / 2 + 5 3"
result3 = evaluate(expression3)
print(f"'{expression3}' = {result3}") 预期输出: '10 / 2 + 5 3' = 20
```
整个流程的总结与回顾
我们一步步地构建了一个简单的表达式解释器。让我们回顾一下这个过程：
1. 词法分析 (Lexing):
将原始的字符串算式（如 `"3 + 4 (2 1)"`）分解成一个个有意义的“记号”（Tokens），例如 `[Token(INTEGER, 3), Token(PLUS, '+'), Token(INTEGER, 4), Token(MULTIPLY, ''), ...]`。
我们定义了 `Token` 类来表示这些记号的类型和值。
`tokenize` 函数负责这个过程。
2. 语法分析 (Parsing):
根据预定义的语法规则（运算符优先级、括号匹配等），将记号列表组织成一个结构化的表示——抽象语法树（AST）。
`AST` 类作为基类，`Num` 和 `BinOp` 是具体的节点类型。
`Parser` 类实现了递归下降解析，通过 `factor`, `term`, `expr` 方法来处理不同的优先级和结构。
3. 求值 (Evaluation):
遍历 AST，根据节点代表的运算执行实际的计算。
`Interpreter` 类使用访问者模式 (`visit` 方法) 来处理不同类型的节点。
`visit_BinOp` 执行运算，`visit_Num` 返回数字本身。
整个过程就像我们人类计算数学题一样：先看懂算式里都有啥（词法分析），再弄清楚先算哪一部分，后算哪一部分（语法分析），最后一步一步地算出结果（求值）。
还可以往哪儿发展？
这个解释器虽然简单，但已经展示了核心原理。要让它更强大，还可以做很多事情：
浮点数支持: 修改 `tokenize` 和 `visit_Num` 来处理 `1.5` 这样的数字，以及在除法时使用浮点运算。
变量: 引入 `IDENTIFIER` 记号类型，并在 `Interpreter` 中维护一个变量字典。`visit_Identifier` 方法会从字典中查找变量值。
函数调用: 比如 `sin(3.14)`。这需要新的记号类型，以及在 AST 中表示函数调用的节点类型，并在 `Interpreter` 中实现函数调用逻辑（可能需要一个函数查找表）。
一元运算符: 例如 `5`。这需要修改 `factor` 函数来处理前导的 `` 号。
更多运算符: 比如取模 `%`，幂 `` 等。
错误处理: 目前的错误处理比较粗糙，可以做得更精细，给出更友好的错误信息。
写在最后
希望这番“唠叨”能让你对如何写一个简单的表达式解释器有个清晰的认识。从字符串到抽象的计算结构，再到最终的结果，这中间的每一步都充满了编程的智慧。
写完这些代码，你是不是感觉自己像一个“数字世界的翻译家”？从人类能理解的语言，翻译成计算机能执行的指令。这正是编程的魅力所在。
如果你有兴趣，不妨试试给它加点新功能，让它变得更强大、更智能。祝你编程愉快！
网友意见
eval只支持解析Python的表达式语法，并且存在注入式攻击漏洞。如果想要快速构建任意表达式语法的解释器，推荐使用pyparsing库。下面摘自它的GitHub Wiki：
Combined with a fear/dismay at using regular expressions, I wanted an object-assembly model for building up parsers. Since then, tools of this style have come to be called PEG's, orParsing Expression Grammars. I also related to Python's operator overloading features, and so pyparsing has become an embedded DSL within Python, making heavy use of operators for grammar construction and call syntax for grammar element naming.
翻译过来就是：「由于使用正则表达式让我恐惧/沮丧，我希望能有一个用于构建解释器的面向对象的框架。从那时起，这种类型的工具逐渐被称做PEG（Parsing Expression Grammars，即解析表达式语法）。PyParasing已经成为嵌入在Python语法中的领域专用语言，并且引入了Python的运算符重载特性。通过它，你可以方便地使用运算符进行语法构造，并可以为可调用的语法产生式符号进行命名。」可以参考一下我的这篇文章：
类似的话题
本站所有内容均为互联网搜索引擎提供的公开搜索信息，本站不存储任何数据与内容，任何内容与数据均与本站无关，如有需要请联系相关搜索引擎包括但不限于百度，google,bing,sogou 等
© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有