Python中如何使用递归函数将表达式tokens转换为指定结构运算树

核心实现基于递归下降+优先级匹配思路，不需要引入第三方库，完全匹配要求的两种转换规则。 #

前置定义 #

首先明确运算符优先级，数字、括号做特殊处理：

# 优先级数值越小，运算优先级越低，在语法树中越靠近上层
OP_PRIORITY = {
    '+': 1,
    '-': 1,
    '*': 2,
    '/': 2
}

辅助函数：括号位置匹配 #

处理括号结构前，需要先定位每个左括号对应的右括号索引，避免误判括号内部的运算符：

def find_matching_bracket(tokens, start_idx):
    """start_idx 必须是左括号'('的索引，返回对应配对右括号的索引"""
    count = 0
    for i in range(start_idx, len(tokens)):
        if tokens[i] == '(':
            count += 1
        elif tokens[i] == ')':
            count -= 1
            if count == 0:
                return i
    raise ValueError("括号不匹配")

核心递归转换函数 #

递归逻辑遵循三个处理顺序：

• 边界判定：当前处理段只有单个数字，直接包装为叶子节点[数字]
• 括号识别：如果当前处理段是括号包裹的内容，先递归处理括号内部表达式，再套入要求的[[内部处理结果], "(", []]结构
• 优先级拆分：遍历当前段，跳过所有括号内部的内容，找到优先级最低、位置最靠右的运算符作为当前层的根节点，将tokens拆分为运算符左右两段，分别递归处理后拼接为当前层结构

def tokens_to_tree(tokens):
    # 边界情况：单个数字，返回叶子节点
    if len(tokens) == 1:
        return [tokens[0]]
    
    # 先检查当前段是否被完整括号包裹
    if tokens[0] == '(':
        match_rb = find_matching_bracket(tokens, 0)
        if match_rb == len(tokens) - 1:
            # 整段被括号包裹，处理内部后套括号结构
            inner_tree = tokens_to_tree(tokens[1:-1])
            return [inner_tree, "(", []]
    
    # 寻找当前层的拆分运算符：优先级最低、不在括号内、最靠右的运算符
    split_idx = -1
    current_lowest_pri = float('inf')
    i = 0
    while i < len(tokens):
        if tokens[i] == '(':
            # 跳过整个括号段，不处理内部运算符
            i = find_matching_bracket(tokens, i) + 1
            continue
        if tokens[i] in OP_PRIORITY:
            op_pri = OP_PRIORITY[tokens[i]]
            # 同优先级选最靠右的，适配左结合运算规则
            if op_pri <= current_lowest_pri:
                current_lowest_pri = op_pri
                split_idx = i
        i += 1
    
    if split_idx == -1:
        raise ValueError(f"无效表达式段: {tokens}")
    
    # 拆分左右段递归处理
    left_part = tokens[:split_idx]
    op = tokens[split_idx]
    right_part = tokens[split_idx+1:]
    
    return [tokens_to_tree(left_part), op, tokens_to_tree(right_part)]

效果验证 #

直接跑给出的两个示例，输出完全匹配规则：

# 测试1：无括号的四则运算
test1 = ["12", "+", "2", "*", "3"]
print(tokens_to_tree(test1))
# 输出：[['12'], '+', [['2'], '*', ['3']]]

# 测试2：带括号的运算
test2 = ["(", "2", "+", "3", ")", "*", "7"]
print(tokens_to_tree(test2))
# 输出：[[[['2'], '+', ['3']], '(', []], '*', ['7']]

扩展说明 #

如果后续需要支持更高优先级的运算符（比如幂运算**、取模%），只需要在OP_PRIORITY字典里补充对应运算符和优先级数值即可，不需要修改核心递归逻辑。

内容的提问来源于stack exchange，提问作者gina