Python:读取具有树深度级别的列表，并输出类似嵌套列表的树 [英] Python: Read a list with tree depth level and output a tree like nested list

问题描述

所以这是我的问题:

我已成功将具有行缩进级别的文本文件解析为以下列表:

I have successfully parsed a text file with line indention level in to a list like:

A = [[1,'a'],[1,'b'],[2,'c'],[2,'d'],[1,'e'],[2,'f']]

列表 A 中的每个元素都是长度为2的列表.每个元素对应于从文本文件读取的一行. A [x] [0] 是文本文件中行的缩进级别， A [x] [1] 是内容的行，其中 x 是 A 中任何元素的索引.

Each element in list A is a list of length 2. Each element corresponds to a line read from the text file. A[x][0] is the indent level of the line in the text file, A[x][1] is the content of the line where x is the index of any element in A.

例如 A [1] = [1，'b'] ，其中 1 是缩进级别，而'b'是行文本. A [2] 和 A [3] 是 A [1] 的子级，即，缩进线.

For e.g. A[1] = [1,'b'] where 1 is the indent level and 'b' is the line text. A[2] and A[3] are children of A[1] i.e. sub indented lines.

我正在尝试获取以下格式的输出列表:

I am trying to get an output list which will be in the following format:

B = [['a'],['b',['c','d']],['e',['f']]]

这样，当我遍历 B [x] [0] 时，我将仅获得第一级缩进项，并且能够递归地访问每个元素.

This way when I iterate over B[x][0] I will get only the first level indented items and be able to recursively go to each element.

该算法应能够处理无限深度，即如果 A [3] 后跟元素 [3，'z'] ，则该嵌套列表应为 A [3] .

The algorithm should be able to handle infinite depth i.e if A[3] was followed by element [3,'z'] it should be a nested list of A[3].

我浏览了其他一些解决类似问题的文章，并使用了 itertools.groupby ，但不幸的是，他们对这些问题的理解还不够，无法将其应用于我的问题.

I have explored some other posts that solve a similar problem and use itertools.groupby but unfortunately haven't been able to understand them enough to be able to apply it to my problem.

真的很感谢您的帮助！

推荐答案

尝试以下基于堆栈的简单算法:

Try this simple stack-based algorithm:

A = [[1,'a'],[1,'b'],[2,'c'],[2,'d'],[1,'e'],[2,'f']]
stack = [ [] ]
for level, item in A:
    while len(stack) > level:
        stack.pop()
    while len(stack) <= level:
        node = (item, [])
        stack[-1].append(node)
        stack.append(node[1])

result = stack[0]

这将创建一个结构，如:

This creates a structure like:

[('a', []), ('b', [('c', []), ('d', [])]), ('e', [('f', [])])]

IMO 使用起来更方便，但如果需要，将其转换为您的应该没问题:

which, IMO, is more convenient to work with, but it should be no problem to convert it to yours if needed:

def convert(lst):
    return [ [x, convert(y)] if y else x for x, y in lst]

result = convert(stack[0])
print result
# ['a', ['b', ['c', 'd']], ['e', ['f']]]

这篇关于Python:读取具有树深度级别的列表，并输出类似嵌套列表的树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！