Python 后缀表示法逆波兰表示法的预排序

Question

我正在尝试在 Python 中找到一个解决方案，尝试将预订符号例如“* + 7 3 - 2 9”或“+ 55 26”移动到 post 符号或逆波兰符号。预期的结果是例如分别为“7 3 + 2 9 - *”和“55 26 +”。我对二叉树做了一些研究，但是我正在努力使用数学函数。我目前拥有的是：

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

检查运算符的函数

def isOperator(self, c):
    return c == '+' or c == '-' or c == '*' or c == '/'

插入节点

def insert(self, data):

    if self.data:
        if data < self.data:
            if self.left is None:
                self.left = Node(data)
            else:
                self.left.insert(data)
        elif data > self.data:
            if self.right is None:
                self.right = Node(data)
            else:
                self.right.insert(data)
    else:
        self.data = data

打印树

def PrintTree(self):
    if self.left:
        self.left.PrintTree()
    print( self.data),
    if self.right:
        self.right.PrintTree()

前序遍历

根 -> 左 -> 右

def PreorderTraversal(self, root):
    res = []
    if root:
        res.append(root.data)
        res = res + self.PreorderTraversal(root.left)
        res = res + self.PreorderTraversal(root.right)
    return res

后序遍历

左 -> 右 -> 根

def PostorderTraversal(self, root):
    res = []
    if root:
        res = self.PostorderTraversal(root.left)
        res = res + self.PostorderTraversal(root.right)
        res.append(root.data)
    return res

非常感谢任何帮助完成此代码的帮助，因为我无法解决这个问题。

提前致谢

Answer 1

首先是一些问题：

您的insert方法应用二叉搜索树逻辑，这与您要构建的表达式树无关。相反，它应该跟踪任何下一个数据的插入点。
不清楚这些是否都是Nodeclass的方法，但至少isOperator与任何实例值无关，所以应该不是方法（带有 self 参数），而是独立函数或静态方法。此外，如果输入有效，则运算符是任何非数字的东西。
方法不应打印（调试目的除外）：留给主要驱动程序代码去做。方法可以通过返回迭代器或表示（实现 __repr__）来帮助打印。
通常的做法是不对函数名称使用首字母大写，并将其保留给 class 个名称。
我建议为树单独 class。这将很方便地跟踪下一个节点应该插入的位置，使用路径（堆栈）。

以下是实现方法：

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

    def __iter__(self):  # default iteration is inorder
        if self.left:
            yield from self.left
        yield self.data
        if self.right:
            yield from self.right

    def preorder(self):
        yield self.data
        if self.left:
            yield from self.left.preorder()
        if self.right:
            yield from self.right.preorder()

    def postorder(self):
        if self.left:
            yield from self.left.postorder()
        if self.right:
            yield from self.right.postorder()
        yield self.data


class Tree:
    def __init__(self):
        self.root = None
        self.path = []

    def insert(self, data):
        if not self.root:
            node = self.root = Node(data)
        elif not self.path:
            raise ValueError("Cannot add more nodes")
        elif self.path[-1].left:
            node = self.path[-1].right = Node(data)
        else:
            node = self.path[-1].left = Node(data)
        if not data.isnumeric(): # internal node
            self.path.append(node)
        else:
            while self.path and self.path[-1].right:
                self.path.pop()
            
    @staticmethod
    def fromstr(s):
        tree = Tree()
        for token in s.split():
            tree.insert(token)
        return tree

    def __iter__(self):
        if self.root:
            yield from self.root

    def preorder(self):
        if self.root:
            yield from self.root.preorder()

    def postorder(self):
        if self.root:
            yield from self.root.postorder()

这里是运行的方法：

def postorder(s):
    tree = Tree.fromstr(s)
    # Just for debugging, print the tree in inorder:
    print(*tree)  # this calls `__iter__`
    return " ".join(tree.postorder())

print(postorder("* + 7 3 - 2 9"))

输出（中序和后序）：

7 + 3 * 2 - 9
7 3 + 2 9 - *

Python 后缀表示法逆波兰表示法的预排序

Python pre-order to postfix notation reverse polish notation

algorithm

binary-tree

python-3.x