构建你的第一个表达式树（Python实现详解：从零开始理解表达式解析与抽象语法树）

什么是表达式树？

表达式树是一种抽象语法树（Abstract Syntax Tree, AST），其中：

• 叶子节点是操作数（如数字、变量）
• 非叶子节点是运算符（如 +、-、*、/）

例如，表达式 3 + 4 * 2 对应的表达式树如下：

      +     / \    3   *       / \      4   2

步骤一：定义树节点类

首先，我们需要一个类来表示树中的每个节点：

class TreeNode:    def __init__(self, value):        self.value = value        self.left = None        self.right = None    def __repr__(self):        return f"TreeNode({self.value})"

步骤二：将中缀表达式转为后缀表达式

为了方便构建树，我们通常先将人类习惯的中缀表达式（如 3 + 4）转换为后缀表达式（也叫逆波兰表达式，如 3 4 +）。这里使用经典的调度场算法（Shunting Yard Algorithm）。

def infix_to_postfix(expression):    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}    output = []    operator_stack = []    tokens = expression.replace(' ', '')  # 去除空格    i = 0    while i < len(tokens):        char = tokens[i]        if char.isdigit():            num = ''            while i < len(tokens) and tokens[i].isdigit():                num += tokens[i]                i += 1            output.append(num)            continue        elif char in precedence:            while (operator_stack and                   operator_stack[-1] != '(' and                   precedence.get(operator_stack[-1], 0) >= precedence[char]):                output.append(operator_stack.pop())            operator_stack.append(char)        elif char == '(':            operator_stack.append(char)        elif char == ')':            while operator_stack and operator_stack[-1] != '(':                output.append(operator_stack.pop())            operator_stack.pop()  # 弹出 '('        i += 1    while operator_stack:        output.append(operator_stack.pop())    return output

步骤三：根据后缀表达式构建表达式树

后缀表达式的特性非常适合用栈来构建树：

def build_expression_tree(postfix):    stack = []    for token in postfix:        if token.isdigit():            node = TreeNode(int(token))            stack.append(node)        else:            # 运算符：弹出两个操作数            right = stack.pop()            left = stack.pop()            node = TreeNode(token)            node.left = left            node.right = right            stack.append(node)    return stack[0]  # 根节点

步骤四：遍历与求值

我们可以递归地对表达式树进行中序遍历（还原表达式）或后序遍历（求值）：

def evaluate_tree(node):    if node is None:        return 0    if node.left is None and node.right is None:        return node.value  # 叶子节点：数字    left_val = evaluate_tree(node.left)    right_val = evaluate_tree(node.right)    if node.value == '+':        return left_val + right_val    elif node.value == '-':        return left_val - right_val    elif node.value == '*':        return left_val * right_val    elif node.value == '/':        return left_val / right_val# 示例使用expr = "3 + 4 * 2"postfix = infix_to_postfix(expr)tree_root = build_expression_tree(postfix)result = evaluate_tree(tree_root)print(f"表达式 '{expr}' 的结果是: {result}")  # 输出: 11

总结

通过本教程，你已经掌握了如何用 Python 实现一个基本的表达式解析系统，并构建了对应的表达式树。这项技能不仅有助于理解编译原理，还能应用于计算器开发、公式引擎、甚至 AI 中的符号推理。

记住，核心的Python数据结构——树，配合抽象语法树的思想，是处理结构化文本的强大工具。继续练习，尝试支持括号、负数、甚至函数调用吧！