Skip to main content
 首页 » 编程设计

python之使用 python 解析树

2024年11月01日11artech

我必须编写一个程序来解析使用一组括号和数字表示的树。所以每个括号代表树中的节点,程序应该打印出每个父节点的所有子节点。 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']}

有什么意见吗??

请您参考如下方法:

我刚刚看了你的一些代码。它没有太多时间,所以我无法真正调试它更多,但您也可以通过以属于的方式使用 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, [])