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, []), Tree(3, [Tree(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 += "]),"

score 2 · Accepted Answer

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

1 2 5 NIL 3 4 NIL NIL NIL NIL

你说这应该是结果（注意我只是格式化了你的版本以便于理解）：

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

“看起来像”这样：

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

从理论上的根节点开始，被认为是“当前”节点。
对于每个非 NIL 值，将其添加为当前节点的子节点，并将其标记为新的当前节点。也就是下降。
对于每个 NIL 值，将当前节点的父节点标记为新的当前节点。也就是登高。
当再次到达理论上的根节点时，我们就完成了（字符串应该被完全消耗掉）。

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

根据我上面给出的大纲，它可以以迭代方式实现，无需递归。有些人更喜欢递归解决方案，但任何一种方式都同样强大，所以后者留作练习！

score 0 · Accepted Answer

因此，假设我们知道以下两件事：

如果您从输入字符串中读取 NIL，您就知道您已读取并清空了树。
如果您读取一个数字，那么您有一个根包含该数字的非空树，您仍然需要从输入字符串中读取两棵树（一棵用于左孩子，一棵用于右孩子）。

现在我们准备好阅读树了:)。假设以下类似 C 的结构（我会让你在 python 中这样做作为练习，并且在 python 中更干净）：

struct tree {
   int value;
   tree *left;
   tree *right;
}

并且有些挥手基本上是一种采用char *的方法，返回第一个标记并将输入字符串更改为指向下一个标记）在输入流中可以执行以下操作：

tree *readTree(char *&inputString) {
   char *token = read_next_token(inputString); 
   if (strcmp(token, "NIL") {
      // empty tree .. we return
      return NULL;
   }

   struct tree* node = malloc(sizeof(struct tree));
   node->value = token_as_int(token);

   // note that after the readTree is called the inputString will be modified
   // that's why i defined it to take a reference to a pointer of chars.
   node->left = readTree(inputString);
   node->right = readTree(inputString);
   return node; 
}

并且 read_next_token 定义为：

char *read_next_token(char*&inputString) {
  char *token = inputString;

  while ( *inputString != ' ' )
    inputString++;

  *inputString = 0; // make the token a null terminated string.

  while ( *inputString == ' ' ) inputString++;

  return token;
}

score 0 · Accepted Answer

也许是这样的：

#! /usr/bin/python3.2

class Tree:
    def __init__ (self, value):
        self.value = value
        self.parent = None
        self.children = []

    def __iadd__ (self, child):
        child.parent = self
        self.children.append (child)
        return self

    def fromString (string):
        return Tree.fromList (string.split () ) [0]

    def fromList (list):
        node = Tree (list [0] )
        list = list [1:]
        while list [0] != 'NIL':
            child, list = Tree.fromList (list)
            node += child
        return node, list [1:]

    def __repr__ (self):
        return '{}{}'.format (self.value, ': {}'.format (self.children) if self.children else '')

t = Tree.fromString ('1 2 5 NIL 3 4 NIL NIL NIL NIL')
print (t)

t = Tree.fromString ('1 2 NIL 3 4 NIL 5 NIL 6 NIL NIL 7 NIL NIL')
print (t)

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

3 回答 3

Related

Reference