python - 在 python 中使用括号从表示二叉树的字符串创建数组

Question

我有一个像这样的字符串:

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

该字符串代表以下二叉树:

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

现在我正在尝试编写一些算法以将其放入数组中，例如:

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

我尝试的第一件事是做类似的事情:

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]

这将分割前两个子树中的字符串。但我不知道如何继续以及如何正确构建数组或相等列表。

非常感谢您的每一次帮助!

Answer 1

您已经非常接近解决方案了，因为您已经完成了解析部分。您只需要修复一些小错误，递归应用您的函数，然后创建字典。

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}

演示:

>>> 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': '+'}