Parsing a tree using python

Question

I have to make a program that parses a tree represented using a set parenthesis and numbers. So each parenthesis represent node in a tree and the program is supposed to print out all the children nodes for each parent node. The python code is as follows:

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)

The result have to be this.

If I print out the list in the make_tree function, I get correct result... But the final result is not correct. In this case, I am missing {'3':['4','5']}

Any comment??

Answer 1

I just looked at some of your code. It didn't have much time so I couldn't have really debugged it way more but you can also implement by having tmpList in the way belong and basically keep updating at every point. Alko's solution works as well, but this might be a bit more clear.

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

You call this by:

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

Answer 2

You overwrite child results with assignment to temp_list, you probably want instead do:

for child in obj.children:
    temp_list += child.traverse(len(child.children), child)