Разбор файла Python: сборка дерева из текстового файла

У меня есть текстовый файл с отступом, который будет использоваться для построения дерева. Каждая строка представляет node, а отступы представляют глубину, а также node текущий node является дочерним элементом.

Что указывает, что ROOT содержит троих детей: 1, 5 и 6, Node1 имеет один ребенок: 2, а Node2 имеет один ребенок: 3 и т.д.

Я придумал рекурсивный алгоритм и запрограммировал его, и он работает, но он вроде уродлив и особенно очень грубо обрабатывает пример выше (при переходе от node 4 до node 5)

В качестве основы для рекурсии используется "подсчет отступа", поэтому, если число отступов = текущая глубина + 1, я бы пошел на один уровень глубже. Но это означает, что когда я читаю строку с меньшим количеством отступов, я должен возвращаться на один уровень за раз, проверяя глубину каждый раз.

Сейчас я просто распечатываю узлы, чтобы убедиться, что родительский node правильный для каждой строки, но, возможно, есть более чистый способ сделать это? Особенно это касается блока elif, когда я возвращаюсь от каждого вызова рекурсии.

Ответы

Ответ 1

Большая проблема - это "взгляд", который, я думаю, вызвал уродство. Его можно немного укоротить:

def _recurse_tree(parent, depth, source):
    last_line = source.readline().rstrip()
    while last_line:
        tabs = last_line.count('\t')
        if tabs < depth:
            break
        node = last_line.strip()
        if tabs >= depth:
            if parent is not None:
                print "%s: %s" %(parent, node)
            last_line = _recurse_tree(node, tabs+1, source)
    return last_line

inFile = open("test.txt")
_recurse_tree(None, 0, inFile)

Поскольку мы говорим о рекурсии, я старался избегать любых глобальных переменных (source и last_line). Было бы более pythonic сделать их членами на каком-то парсерном объекте.

Ответ 2

Если вы не настаиваете на рекурсии, это тоже работает:

from itertools import takewhile

is_tab = '\t'.__eq__

def build_tree(lines):
    lines = iter(lines)
    stack = []
    for line in lines:
        indent = len(list(takewhile(is_tab, line)))
        stack[indent:] = [line.lstrip()]
        print stack

source = '''ROOT
\tNode1
\t\tNode2
\t\t\tNode3
\t\t\t\tNode4
\tNode5
\tNode6'''

build_tree(source.split('\n'))

Результат:

['ROOT']
['ROOT', 'Node1']
['ROOT', 'Node1', 'Node2']
['ROOT', 'Node1', 'Node2', 'Node3']
['ROOT', 'Node1', 'Node2', 'Node3', 'Node4']
['ROOT', 'Node5']
['ROOT', 'Node6']

Ответ 3

Я бы не использовал рекурсию для чего-то вроде этого (ну, может быть, я бы, если бы я кодировал это на языке, таком как Scheme, но здесь Python). Рекурсия отлично подходит для повторения данных, которые имеют форму дерева, и в этих случаях это значительно упростит ваш дизайн по сравнению с обычными циклами.

Однако здесь это не так. Ваши данные, безусловно, представляют собой дерево, но они форматируются последовательно, т.е. Это простая последовательность строк. Такие данные наиболее легко обрабатываются простым циклом, хотя вы могли бы сделать дизайн более общим, если хотите, разделяя его на три разных слоя: последовательный читатель (который будет анализировать вкладки как спецификацию уровня глубины), (который вставляет node в дерево на определенном уровне глубины, отслеживая последний node, который был вставлен в дерево) и само дерево:

import re

# *** Tree representation ***
class Node(object):
    def __init__(self, title):
        self.title = title
        self.parent = None
        self.children = []

    def add(self, child):
        self.children.append(child)
        child.parent = self

# *** Node insertion logic ***
class Inserter(object):
    def __init__(self, node, depth = 0):
        self.node = node
        self.depth = depth

    def __call__(self, title, depth):
        newNode = Node(title)
        if (depth > self.depth):
            self.node.add(newNode)
            self.depth = depth
        elif (depth == self.depth):
            self.node.parent.add(newNode)
        else:
            parent = self.node.parent
            for i in xrange(0, self.depth - depth):
                parent = parent.parent
            parent.add(newNode)
            self.depth = depth

        self.node = newNode

# *** File iteration logic ***
with open(r'tree.txt', 'r') as f:    
    tree = Node(f.readline().rstrip('\n'))
    inserter = Inserter(tree)

    for line in f:
        line = line.rstrip('\n')
        # note there a bug with your original tab parsing code:
        # it would count all tabs in the string, not just the ones
        # at the beginning
        tabs = re.match('\t*', line).group(0).count('\t')
        title = line[tabs:]
        inserter(title, tabs)

Когда мне пришлось протестировать этот код, прежде чем вставлять его здесь, я написал очень простую функцию для правильной печати дерева, которое я читал в память. Для этой функции наиболее естественным было использование рекурсии, конечно, потому что теперь дерево действительно представлено в виде древовидных данных:

def print_tree(node, depth = 0):
    print '%s%s' % ('  ' * depth, node.title)
    for child in node.children:
        rec(child, depth + 1)

print_tree(tree)