如何处理嵌套列表？

Question

假设我有一个这样的项目符号列表:

* list item 1
* list item 2 (a parent)
** list item 3 (a child of list item 2)
** list item 4 (a child of list item 2 as well)
*** list item 5 (a child of list item 4 and a grand-child of list item 2)
* list item 6

我想将其解析为嵌套列表或其他一些数据结构,这使得元素之间的父子关系显式化(而不是依赖于它们的内容和相对位置).例如,这是一个元组列表,其中包含一个项目及其子项列表(等等):

编辑:希望是一个更正确的列表示例,其中列表中的每个元素都是一个元组,其中包含:子弹的文本以及子项列表(如果适用)(以相同的形式).

    [('list item 1',),
     ('list item 2', [('list item 3',), ('list item 4', [('list item 5',)])]
     ('list item 6',)]

[('list item 1',),
 ('list item 2', [('list item 3',), ('list item 4', [('list item 5',)])]),
 ('list item 6',)]

我试图用普通的Python和一些Pyparsing的实验做到这一点,但我没有取得进展.我有两个主要问题:

1. 我需要采用什么策略来完成这项工作？我知道递归是解决方案的一部分,但我很难在这个和斐波那契序列之间建立联系.
2. 我确定我不是第一个这样做的人,但是我不知道问题的术语来搜索关于这个主题的更多信息.有什么问题与此有关,这样我才能更多地了解解决这类问题？

Answer 1

在搜索算法的视图中,您提供的子弹实际上是由Depth-First-Search生成的序列.所以我的策略是用dfs-sequence重建树结构.

以下是python代码:

from collections import deque
def dfsBullet(bullet,depth):
    """
       parse the subtree with depth and the startnode of bullet[0]
    """
    li = []
    if depth != 0:
            item = bullet.popleft()
            li.append(item.split(' ',1)[1])
    while (len(bullet) != 0):
            item = bullet[0]
            #apply same algo to the child node
            if len(item.split(' ',1)[0]) > depth:
                    sublist = dfsBullet(bullet, len(item.split(' ')[0]))
            #we have traverse all childnode, so go back 
            else:
                    return li
            #add child tree to the list
            li.append(sublist)
    return li