How to parse a tree in python?

Question

I have an expression as follow: ( root (AA ( CC) (DD) ) (BB (CC) (DD) ) )

I want to parse this expression using recursion and I created a tree class but I'm stuck after this man.

This looks this the following tree.

 root
 |
 ____________
 AA BB
 | | 
 __________ ___________
 CC DD CC DD

The output should look like this:

Root -> AA BB
AA -> CC DD
BB -> CC DD

My tree class look like the following:

 class tree_parsing(object):
 def __init__(self, element=None):
 self.element = element
 self.children = []

Basically I want to store the children in a list member variable of the class. Can someone help figure this problem out? Thank You.

• Arthur Dent: It would be helpful to know exactly where you're starting from. Is the task to parse the text string "( root (AA ( CC) (DD) ) (BB (CC) (DD) ) )"?
• Hell Man: Yes the input would be a string and spaces can be ignored.
• Jan Henke: Sounds like you want to implement breath first search, wikipedia gives some hints including a rough implementation: en.wikipedia.org/wiki/Breadth-first_search
• Arthur Dent: OK. I'd suggest proceeding as follows: Scan the string left to right. Parse the left parenthesis to mean "start a new tree node class, possibly as a child of the one I'm working on now." Ignore spaces and parse non-parentheses as portions of a name that will be completed by a parenthesis (either open or closed). Closed parenthesis will have a meaning that will become clear as you go, I think. Hopefully, that will give you a start.
• Paulo Bu: BFS should be the last step: the output. But for building the tree, he'll certainly need to write some lexer and parser - which ain't that straightforward.

Answer 1

You can do something like this:

#!python
# -*- coding: utf-8 -*-
class Node(object):
 def __init__(self, name, left=None, right=None):
 self.name = name
 self.left = left
 self.right = right
def dump_tree(node):
 if node.left or node.right:
 left = 'None' if node.left is None else node.left.name
 right = 'None' if node.right is None else node.right.name
 print('{0} -> {1} {2}'.format(node.name, left, right))
 if node.left:
 dump_tree(node.left)
 if node.right:
 dump_tree(node.right)
Root = Node(
 'Root', Node('AA', Node('CC'), Node('DD')),
 Node('BB', Node('CC'), Node('DD')),
)
dump_tree(Root)

prints:

$ python example.py
Root -> AA BB
AA -> CC DD
BB -> CC DD
$