Muszę dokonać programu, który analizuje drzewo reprezentowane za pomocą zestawu nawiasów i numerów. Więc każda nawias reprezentuje węzeł na drzewie, a program ma wydrukować wszystkie węzły dzieci dla każdego węzła nadrzędnego. Kod Pythona jest następujący:

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)

Wynik musi być to. wynik

Jeśli wydrukowam listę w funkcji Make_tree, uzyskuję poprawny wynik ... ale ostateczny wynik nie jest poprawny. W tym przypadku brakuje mnie {'3': ['4', "5 ']} wynik końcowy

Jakiś komentarz??

3
eChung00 24 listopad 2013, 01:12

2 odpowiedzi

Najlepsza odpowiedź

Właśnie spojrzałem na niektórych z twojego kodu. Nie miało dużo czasu, więc nie mogłem go naprawdę debugować, ale możesz również wdrożyć, mając Tmplist w sposobie należącej i zasadniczo aktualizując w każdym punkcie. Działa również rozwiązanie Alko, ale może to być nieco jasne.

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

Nazywasz to:

final = test.traverse(len(test.children), test, [])
1
p0lAris 23 listopad 2013, 22:30

Nadpisujesz wyniki dziecka z przypisaniem do temp_list, prawdopodobnie chcesz zrobić:

for child in obj.children:
    temp_list += child.traverse(len(child.children), child)
1
alko 23 listopad 2013, 22:25