Python表达式二叉树求值代码输出异常修复

核心问题定位 #

原代码无法得到正确结果的原因有三点：

• 缺失Node类的完整定义，仅编写了构造方法无法完成节点实例化
• 依赖全局变量expression拼接字符串，括号匹配逻辑错误，且递归非空分支无返回值，无法在遍历完成时拿到完整合法的表达式
• 未按要求调用eval()方法对合法表达式执行计算，无法输出数值结果

修复后可运行代码 #

这里直接废弃容易出现值污染的全局变量方案，通过递归直接返回子树对应表达式字符串，天然避免全局变量被异常重置的问题：

# 补全Node类定义
class Node:
    def __init__(self, val, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right

PLUS = "+"
MINUS = "-"
TIMES = "*"
DIVIDE = "/"

def evaluate(root):
    operators = (PLUS, MINUS, TIMES, DIVIDE)
    # 空节点返回空字符串
    if root is None:
        return ""
    # 数字叶子节点直接返回值的字符串形式
    if root.left is None and root.right is None:
        return str(root.val)
    # 递归拼接左右子树的表达式，对子表达式加括号保证运算优先级
    left_part = evaluate(root.left)
    right_part = evaluate(root.right)
    sub_expr = f"({left_part}{root.val}{right_part})"
    # 根节点层去掉最外层多余括号后执行eval计算
    return eval(sub_expr[1:-1])

# 构建测试表达式树 对应运算(3+2)*(4+5)
#     *
#    / \
#   +    +
#  / \  / \
# 3  2  4  5
tree = Node(TIMES)
tree.left = Node(PLUS)
tree.left.left = Node(3)
tree.left.right = Node(2)
tree.right = Node(PLUS)
tree.right.left = Node(4)
tree.right.right = Node(5)      

print(evaluate(tree))

运行上述代码会直接输出预期结果45。

如果要保留原代码的全局变量实现逻辑，只需要调整括号拼接规则，在递归执行完成回到根节点调用层时，取全局expression的值调用eval计算即可，注意计算完成后手动重置全局变量值，避免多次调用时出现表达式拼接错乱。

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