如何从符号列表中构建树?

Question

我是python新手。

我有一个像这样定义的树数据结构(我没有写它，它是提供的):

class Tree(object):
def __init__(self, name='root', children=None):
self.name = name
self.children = []
if children is not None:
for child in children:
self.add_child(child)
def __repr__(self):
return self.name
def add_child(self, node):
assert isinstance(node, Tree)
self.children.append(node)

下面的函数显示树:

def display_tree(root, indent=0):
print(' ' * indent, root)
if len(root.children) > 0:
for child in root.children:
display_tree(child, indent+4)

现在，我有一个符号列表，像这样:

symbols = ['a', '[', 'b', '[', 'c', 'd', 'e', ']', 'f', '[', 'g', 'h', '[', 'i', ']', '1j', '[', 'k', 'l', ']', ']', 'm', ']']

我需要能够得到如下的树:

a
b
c
d
e
f
g
h
i
j
k
l
m   

我发现下面的代码行给了我需要的结果:

t = Tree('a',[Tree('b',[Tree('c'),
Tree('d'),
Tree('e')]),
Tree('f',[Tree('g'),
Tree('h',[Tree('i')]),
Tree('j',[Tree('k'),
Tree('l')])]),
Tree('m')])

display_tree(t)

那么我如何将符号列表转换成上面的"t"形式，以便当我将列表作为输入输入给函数时，我得到树作为输出?

我最初的想法是使用堆栈数据结构，并不断将符号推到堆栈上，直到我遇到']'，然后通过从堆栈中弹出元素来构建树。但这并没有保持顺序，而且我对python的精通程度也不足以实现这一点。

Answer 1

可以使用递归堆栈。下面是一个从这些符号构建树的递归函数:

def tree_from_symbols(symbols):
it = iter(symbols)

def recur(delimiter=None):
nodes = []
while True:
symbol = next(it, None)
if symbol == delimiter:
return nodes
if symbol == "[":
for child in recur("]"):
nodes[-1].add_child(child)
else:
nodes.append(Tree(symbol))
roots = recur()
if len(roots) > 1:
raise ValueError("The root is not unique")
if len(roots) == 1:
return roots[0]