Python文件解析:从文本文件构建树

Question

我有一个缩进的文本文件,将用于构建一个树.每行代表一个节点,缩进代表深度以及当前节点是其子节点的节点.

例如,文件可能看起来像

ROOT
   Node1
      Node2
         Node3
            Node4
   Node5
   Node6

这表明ROOT包含三个子节点:1,5和6,Node1有一个子节点:2,Node2有一个子节点:3,等等.

我已经提出了一个递归算法并对它进行了编程并且它可以正常工作,但它有点难看,特别是对上面的例子非常粗略(从节点4到节点5)

它使用"缩进计数"作为递归的基础,因此如果缩进的数量=当前深度+ 1,我会更深一层.但这意味着当我读取一个较少缩进的行时,我必须一次返回一个级别,每次检查深度.

这就是我所拥有的

def _recurse_tree(node, parent, depth):
    tabs = 0

    while node:
        tabs = node.count("\t")
        if tabs == depth:
            print "%s: %s" %(parent.strip(), node.strip())
        elif tabs == depth + 1:
            node = _recurse_tree(node, prev, depth+1)
            tabs = node.count("\t")

            #check if we have to surface some more
            if tabs == depth:
                print "%s: %s" %(parent.strip(), node.strip())
            else:
                return node
        else:
            return node

        prev = node
        node = inFile.readline().rstrip()

inFile = open("test.txt")
root = inFile.readline().rstrip()
node = inFile.readline().rstrip()
_recurse_tree(node, root, 1)

现在我只是打印出节点来验证父节点对于每一行是否正确,但是可能有更简洁的方法呢？当我从每次递归调用回来时,特别是elif块中的情况.

Answer 1

如果你不坚持递归,这也适用:

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']

Answer 2

最大的问题是我认为造成丑陋的"先行".它可以略微缩短:

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.

Answer 3

我根本不会对这样的事情使用递归(好吧,如果我用一种像Scheme这样的语言编写它,也许我会这样做,但这是Python).递归非常适合迭代形状像树的数据,在这种情况下,与普通循环相比,它会大大简化您的设计.

但是,这不是这种情况.您的数据肯定代表一棵树,但它是按顺序格式化的,即它是一个简单的行序列.这样的数据是最容易用一个简单的循环处理时,虽然可以使设计更一般地,如果希望,通过将其分离成三个不同的层:所述顺序读取器(其将解析的标签作为深度级别的规格),则树插入器(通过跟踪插入树中的最后一个节点,将节点插入特定深度级别的树中)和树本身:

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's 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)