如何處理嵌套列表？

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

我無法解析您想要的結果 - 它似乎有更開放的括號比相應的封閉的人，我不明白它背後的邏輯。

爲了讓樹結構明確的，怎麼樣，例如：

data = '''* list item 1 
* list item 2 
** list item 3 
** list item 4 
*** list item 5 
* list item 6'''.splitlines() 

class Node(object): 
    def __init__(self, payload): 
    self.payload = payload 
    self.children = [] 
    def show(self, indent): 
    print ' '*indent, self.payload 
    for c in self.children: 
     c.show(indent+2) 

def makenest(linelist): 
    rootnode = Node(None) 
    stack = [(rootnode, 0)] 
    for line in linelist: 
    for i, c in enumerate(line): 
     if c != '*': break 
    stars, payload = line[:i], line[i:].strip() 
    curlev = len(stars) 
    curnod = Node(payload) 
    while True: 
     parent, level = stack[-1] 
     if curlev > level: break 
     del stack[-1] 
    # a child node of the current top-of-stack 
    parent.children.append(curnod) 
    stack.append((curnod, curlev)) 
    rootnode.show(0) 

makenest(data) 

當然，show方法存在只是爲了驗證關於解析字符串和創造樹中的一部分已經工作正常的目的。如果你可以更準確地指定它是如何將你的樹轉換成嵌套元組和列表的，我相信它很容易添加到類Node適當的（也許遞歸）方法 - 所以，你能請給這個缺少的規範...？

編輯：由於OP現在已經闡明，它的確如預測的那樣容易滿足規範。只需添加到class Node下面的方法：

def emit(self): 
    if self.children: 
     return (self.payload, 
       [c.emit() for c in self.children]) 
    else: 
     return (self.payload,) 

，並更改最後三行代碼（的makenest最後一個，一個空白的，和模塊級呼叫makenest）來：

return [c.emit() for c in rootnode.children] 

print(makenest(data)) 

（print之後的括號在Python 2中是多餘的但無害的，在Python 3中是必需的，所以我把它們放在那裏以防萬一;-)。

通過這些微小的變化，我的代碼運行的要求，現在發射

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

Answer 2

跟蹤您正在解析的當前「深度」。

• 如果下一行的深度大於當前深度，則遞歸調用具有新深度的解析器，然後將該調用的結果添加到當前列表中。
• 如果下一行的深度等於當前深度，請將其添加到當前列表中。
• 如果下一行的深度小於當前深度，則返回當前列表。

Answer 3

在搜索算法的視圖中，您給出的子彈實際上是由深度優先搜索生成的序列。所以我的策略是用dfs序列重建樹結構。

以下是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