在Python中将前缀转换为后缀表达式

Question

我是一名初学者，现在已经学习Python几个月了。

尝试使用树法解决主题问题，但没有成功。但是，我无法确定哪个不起作用。

    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].isdigit():
                # If the current character is a digit, create a node
                # with the digit and push it to the stack
                node = Node(expression[i])
                stack.append(node)
            else:
                # If the current character is an operator, pop two nodes
                # from the stack and create a new node with the operator
                # as the root, and the popped nodes as its left and right children
                left = stack.pop()
                right = stack.pop()
                node = Node(expression[i])
                node.left = left
                node.right = right
                stack.append(node)

        root = stack.pop()
        postfix = ''
        
    def postorder(root):
        if root:
            postorder(root.left)
            postorder(root.right)
            postfix += root.data
        return postfix

prefix_to_postfix("+*AB-CD")
output: AB*+CD-
expected AB*CD-+

如果有人能指出我正确的方向，我将不胜感激。谢谢。

Answer 1

您为

print(prefix_to_postfix("+*ABC"))

编写的内容会得到错误的输出，但您不可能使用共享的代码获得该输出 - 它会产生错误。

这里有一些问题：

• 缩进错误。

  __init__

  应该是

  Node

  类的方法，而其他两个函数是顶级函数。

• postorder

  引用了一个它不知道的名称：

  postfix

• postorder

  永远不会被

  print(prefix_to_postfix("+*ABC"))

  调用
对于此示例输入，

• isdigit()

  永远不会成立，因此输入中的每个字符都将被视为运算符，并且不会识别任何操作数。

• prefix_to_postfix

  不会返回任何内容，因此

  print(prefix_to_postfix("+*ABC"))

  永远无法打印除

  None

  以外的任何内容

• prefix_to_postfix

  将

  postfix

  设置为空字符串，然后不对其执行任何操作。

• postorder

  被递归调用，但该递归调用返回的值将被忽略。

这是对您的程序的更正：

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

def prefix_to_postfix(expression):  # indentation fixed
    stack = []

    for i in range(len(expression) - 1, -1, -1):
        if expression[i].isalnum():  # consider letters as operands too
            node = Node(expression[i])
            stack.append(node)
        else:
            left = stack.pop()
            right = stack.pop()
            node = Node(expression[i])
            node.left = left
            node.right = right
            stack.append(node)

    root = stack.pop()
    return postorder(root)   # call the other function and return its result
    
def postorder(root):
    postfix = ''  # define this name here
    if root:
        postfix += postorder(root.left)  # don't ignore returned value
        postfix += postorder(root.right)
        postfix += root.data
    return postfix

通过这些修复，我们可以做到：

print(prefix_to_postfix("+*AB-CD"))

输出为：

AB*CD-+