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']} final result

Any comment??

• p0lAris: How do you print out the final? Cause I only see — [{'Root': ['1']}].
• eChung00: @flippex17 just by typing final after I run this code.
• p0lAris: Oh I am sorry, I didn't pay much attention there. I'll look into it.
• eChung00: @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

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)