Создание двоичного дерева из ввода строки

Question

Я пытаюсь создать рекурсивную (или циклическую) функцию, которая принимает строку в качестве входных данных, formate "(2 (1) (3))" (я не беспокоюсь о сортировке он) и интерпретирует его как список в двоичном дереве, таком как [2 [1 [] []] [3 [] []]], чтобы быть простым. Вот что я разработал до сих пор, но он не работает. Вот что у меня до сих пор:

def subtrees(string): 
    tree = [] 
    for x in string: 
     if x == "(": 
      return tree.append(subtrees(string[1:])) 
     elif x == ")": 
      return tree 
     else: 
      tree.append(int(x)) 
      return tree.append(subtrees(string[1:])) 

После обширного тестирования, я нашел две большие ошибки: один из них, что return после того, как находит первые закрытые скобки завершает весь бега функции (а не просто что один рекурсивный вызов для завершения узла), и по какой-то причине, когда я пытаюсь распечатать вывод, он печатает None. Любые подсказки/подсказки будут оценены, так как я действительно очень потерян здесь.

Answer 1

У вас есть ряд проблем с вашей функции:

• list.append() возвращает None
• вы возвращаете для каждого состояния (обычно None из-за выше)
• ваш являются unneccessarily рекурсии для элемента
• ваши рекурсивные функции не продвигают ваши внешние функции, потому что вы передаете копию строки, превратите строку в итерируемый

Быстрые исправления:

def subtrees(string): 
    s = iter(string) 
    tree = [] 
    for x in s: 
     if x == "(": 
      tree.append(subtrees(s)) 
     elif x == ")": 
      return tree 
     else: 
      tree.append(int(x)) 
    return tree[0] 

>>> subtrees('(2(1)(3))') 
[2, [1], [3]]