Python中用树方法实现前缀转后缀表达式出错求助

问题定位 #

你得到的结果AB*+CD-与预期AB*CD-+不符，核心问题出在运算符节点的子树顺序错误，同时代码存在变量作用域、函数调用及判断逻辑的疏漏，导致整体逻辑未正确执行。

具体问题与修复步骤 #

1. 运算符节点的左右子树顺序颠倒 #

处理运算符时，原代码先弹出的节点被设为左子树，后弹出的设为右子树，但由于我们是从右往左遍历前缀表达式，弹出的第一个节点应为当前运算符的右子树，第二个才是左子树。

原错误代码：

left = stack.pop()
right = stack.pop()
node.left = left
node.right = right

修复后：

right = stack.pop()  # 先弹出的是右子树
left = stack.pop()   # 后弹出的是左子树
node.left = left
node.right = right

2. 变量作用域与后序遍历实现错误 #

postorder函数无法访问prefix_to_postfix内定义的postfix变量，直接执行postfix += root.data会抛出未定义异常；同时原代码未调用postorder，也没有返回结果。

建议用列表收集后序遍历结果（避免字符串不可变的性能问题），修复后的完整逻辑：

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def prefix_to_postfix(expression):
    stack = []

    for i in range(len(expression) - 1, -1, -1):
        # 测试用例含字母，需同时匹配字母和数字
        if expression[i].isalpha() or expression[i].isdigit():
            node = Node(expression[i])
            stack.append(node)
        else:
            # 修正子树顺序
            right = stack.pop()
            left = stack.pop()
            node = Node(expression[i])
            node.left = left
            node.right = right
            stack.append(node)

    root = stack.pop()
    postfix = []
    
    def postorder(node):
        if node:
            postorder(node.left)
            postorder(node.right)
            postfix.append(node.data)
    
    postorder(root)
    return ''.join(postfix)

3. 函数缩进与判断逻辑疏漏 #

原代码将prefix_to_postfix和postorder缩进在Node类内部，导致调用逻辑混乱，需修正为独立函数；同时原代码仅判断isdigit()，无法匹配测试用例中的字母操作数，需补充isalpha()判断。

测试验证 #

调用修复后的prefix_to_postfix("+*AB-CD")，将得到预期结果AB*CD-+。

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