Creating an Array out of a string representing a binary tree using brackets in python

Question

I have a string like:

bintree := "((0+(0+1))+(1+1))"

this string represents the following binary tree:

             +
           /   \
          +     +
        /  \   / \
       0    + 1   1
           / \
          0   1

now I'm trying to code some algoritm to get this into an Array like:

array( 'type'  => '+',
       'left'  => array( 'type' => '+',
                         'left' => array( 'type' => '0', 
                                          'left' => False, 
                                          'right'=> False
                                        ),
                         'right' => array( 'type' => '+',
                                           'left' => array( 'type' => 'o'  
                                                            'left' => False, 
                                                            'right'=> False
                                                           ),
                                           'right'=> array( 'type' => '1'  
                                                            'left' => False, 
                                                            'right'=> False),
                                         )
                       )
       'right' => array( 'type' => '+',
                         'left' => array( 'type' => '1', 
                                          'left' => 'False', 
                                          'right' => False,
                                        ),
                         'right' => array( 'type' => '1', 
                                          'left' => 'False', 
                                          'right' => False,
                                        )
                       )
     )

First thing I tried, was to do something like:

def built_array(bintree):
    for char in bintree:
        if char == "(":
           i += 1
        if char == ")":
           i -= 1
        if char == "+" and i == 1
           left = bintree[1:pos]
           right = bintree[pos+1:-1]

That will split the string in the first two sub-trees. But I don’t know how to continue and how to properly build the array or an equal list.

Thanks a lot for every help!

Answer 1

You're very close to the solution, since you got the parsing part done. You just need to fix a few small mistakes, apply your function recursively, and create the dictionaries.

def built_array(bintree):
    # You forgot the initialization
    i = 0
    left = right = ''
    # Also need the current position, use enumerate for that
    for pos, char in enumerate(bintree):
        if char == "(":
           i += 1
        if char == ")":
           i -= 1
        if char == "+" and i == 1:
           left = bintree[1:pos]
           right = bintree[pos+1:-1]
    # Construct the dictionaries
    if left or right:
        return {'type': '+',
                # Apply your function recursively
                'left': built_array(left), 
                'right': built_array(right)}
    else:
        return {'type': bintree,
                'left': None,
                'right': None}

Demo:

>>> built_array("((0+(0+1))+(1+1))")
{'left': {'left': {'left': None, 'right': None, 'type': '0'},
  'right': {'left': {'left': None, 'right': None, 'type': '0'},
   'right': {'left': None, 'right': None, 'type': '1'},
   'type': '+'},
  'type': '+'},
 'right': {'left': {'left': None, 'right': None, 'type': '1'},
  'right': {'left': None, 'right': None, 'type': '1'},
  'type': '+'},
 'type': '+'}