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. Result

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??

How do you print out the final? Cause I only see — [{'Root': ['1']}]. — p0lAris
– p0lAris, Commented Nov 23, 2013 at 21:50
Oh I am sorry, I didn't pay much attention there. I'll look into it. — p0lAris
– p0lAris, Commented Nov 23, 2013 at 21:56
@flippex17 Thank you!! I do not understand why this program prints out correct result but returns a list with missing item.. thanks for your help — eChung00
– eChung00, Commented Nov 23, 2013 at 22:00

p0lAris · Accepted Answer · 2013-11-23 22:30:26Z

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, [])

answered Nov 23, 2013 at 22:30

p0lAris

4,8408 gold badges49 silver badges80 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

alko · Accepted Answer · 2013-11-23 22:25:58Z

1

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)

answered Nov 23, 2013 at 22:25

alko

48.7k12 gold badges99 silver badges105 bronze badges

Collectives™ on Stack Overflow

Parsing a tree using python

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related