后缀表达式的Tokenizer与递归Parser返回错误结果，请求排查

问题概述 #

你为后缀表达式实现了tokenizer和递归解析器，其中tokenizer功能正常，输出的tokens符合预期：

[('NUMBER', '2'), ('NUMBER', '3'), ('NUMBER', '4'), ('OPERATOR', '*'), ('OPERATOR', '+')]

但parse_expression函数返回的解析结果仅为2（预期为('+', 2, ('*', 3, 4))），最终计算结果为2（预期为14）。

错误原因 #

你的parse_expression函数逻辑存在根本性错误：它仅处理第一个token就直接返回，完全忽略了后续的操作数和运算符。

当调用parse_expression处理初始tokens列表时，第一个token是('NUMBER', '2')，函数直接返回整数2，不再处理剩余的[('NUMBER','3'), ('NUMBER','4'), ('OPERATOR','*'), ('OPERATOR','+')]，这直接导致解析结果和计算结果不符合预期。

后缀表达式（逆波兰式）的核心语法规则是操作数 操作数 运算符，递归解析的逻辑需要适配这种“先操作数后运算符”的结构，而当前的递归实现并没有考虑后续token对当前操作数的依赖关系。

修复方案 #

后缀表达式最经典且可靠的处理方式是使用栈结构，以下是修改后的parse_expression函数：

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("后缀表达式格式错误：运算符缺少足够操作数")
            right_operand = stack.pop()
            left_operand = stack.pop()
            # 将运算符和操作数组成表达式元组后入栈
            stack.append((value, left_operand, right_operand))
        else:
            raise ValueError(f"未知token类型：{token_type}")
    # 最终栈中应只剩一个完整表达式
    if len(stack) != 1:
        raise ValueError("后缀表达式格式错误：操作数与运算符数量不匹配")
    return stack[0]

验证结果 #

修改后运行main函数，输出结果如下：

Source code: 2 3 4 * +
Parsed expression: ('+', 2, ('*', 3, 4))
Result: 14

完全符合预期。

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