python - 使用堆栈将字符串解析为树

Question

为了充分披露，这是硬件，但分配已经到期。

如果我们定义一个简单的树如下:

class Tree (object):
    __slots__ = "node","children"
    def __init__(self,node,children=[]):
        self.node = node
        self.children = children

我们如何从字符串构建一棵树？在字符串模型中，“NIL”表示树的结束。因此，字符串 1 2 5 NIL 3 4 NIL NIL NIL NIL 将返回一棵类似于 t = Tree(1, [Tree(2, [Tree(5, [])),树(3，[树(4)])])])。该解决方案可以使用递归和/或堆栈。我以为我理解了堆栈和递归，但我无法弄清楚这个问题。有什么想法吗？

编辑
要添加更多信息，我们可以打印树，如下所示:

def __str__(self):
    return "(%s)" % " ".join(map(str,[self.node]+self.children))

我无法接近创建一棵树并打印它。我所能想到的就是创建一个看起来像创建树的字符串的字符串。我有:

def delinearize(self, linear_string):
    @staticmethod
    tree_data = linear_string.split()
    tree_str = ""
    if tree_data[0] == "NIL":
        print "Tree needs initial root node"
        return
    for entry in tree_data:
        if entry != "NIL":
                tree_str += "Tree("+entry+", ["
        elif entry == "NIL":
                tree_str += "]),"

Answer 1

在您的示例中，对于此输入:

1 2 5 NIL 3 4 NIL NIL NIL NIL

你说这应该是结果(注意我只是格式化你的版本以便于理解):

Tree(1, [
    Tree(2, [
        Tree(5, []),
        Tree(3, [
            Tree(4)
        ])
    ])
])

这“看起来像”:

  1
  |
  2
 / \
5   3
    |
    4

从此(以及 nneonneo 的有用评论)我们可以确定这些树是如何从字符串构建的。它似乎是这样工作的:

1. 从理论上的根节点开始，被视为“当前”节点。
2. 对于每个非 NIL 值，将其添加为当前节点的子节点，并将其标记为新的当前节点。即下降。
3. 对于每个 NIL 值，将当前节点的父节点标记为新的当前节点。即上升。
4. 当再次到达理论上的根节点时，我们就完成了(并且字符串应该被完全消耗)。

请注意，如果您想节省空间，可以省略返回根的尾随 NIL。另一方面，包括它们支持最后的健全性检查。

根据我上面给出的概述，它可以以迭代方式实现，无需递归。有些人更喜欢递归解决方案，但无论哪种方式都同样强大，因此后者留作练习!