python - 使用 python 解析树

Question

我必须编写一个程序来解析使用一组括号和数字表示的树。所以每个括号代表树中的节点，程序应该打印出每个父节点的所有子节点。 python代码如下:

class context(object):
    def __init__(self, label=None, parent=None, children=[]):
        self.label = label
        self.parent = parent
        self.children = []
        self.list = []

    def make_tree(self, tree):
        stack = []
        index = 0
        while index < len(tree):
            if tree[index] is '(':
                if self.label is None:
                    self.label = tree[index+1]
                    index = index+1
                else:
                    if len(stack) == 0:
                        stack.append(context(tree[index+1], self.label))
                        index = index+1
                    else:
                        stack.append(context(tree[index+1], stack[len(stack)-1].label))
                        index = index+1

            elif tree[index] is ')':
                if len(stack) == 1:
                    self.children.append(stack.pop())
                    return
                else:
                    stack[len(stack)-2].children.append(stack.pop())
            index = index+1

    def traverse(self, size, obj):
        if self.label is None or size == 0:
            return []
        temp_list = []
        temp = []
        dic = {}
        tt = [children.label for children in obj.children]
        dic[obj.label] = tt
        temp.append(dic)
        for child in obj.children:
            temp_list = child.traverse(len(child.children), child)
        print temp
        return temp + temp_list


line =  '( Root ( 1 ( 2 )  ( 3 ( 4 )  ( 5 )  )  ( 6 ( 7 )  ( 8 ( 9 )  )  )  )  ) '.split()
test = context()
test.make_tree(line)
final = test.traverse(len(test.children), test)

结果必须是这样的。

如果我在 make_tree 函数中打印出列表，我会得到正确的结果...但最终结果不正确。在这种情况下，我缺少 {'3':['4','5']}

有什么意见吗？？

Answer 1

我刚刚看了你的一些代码。它没有太多时间，所以我无法真正调试它更多，但您也可以通过以属于的方式使用 tmpList 来实现，并且基本上在每个点都保持更新。 Alko 的解决方案也适用，但这可能更清楚一些。

def traverse(self, size, obj, tmpList):
    if self.label is None or size == 0:
        return []
    dic = {}
    tt = [children.label for children in obj.children]
    dic[obj.label] = tt
    tmpList.append(dic)
    for child in obj.children:
        child.traverse(len(child.children), child, tmpList)
    return tmpList

您通过以下方式调用它:

final = test.traverse(len(test.children), test, [])