Как мне обработать вложенный список?

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

Answer 2

Я не могу разобрать желаемый результат - кажется, что в нем больше открытых скобок, чем в соответствующих закрытых, и я не понимаю логику, стоящую за ним.

Чтобы сделать древовидную структуру явной, как насчетНапример:

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 соответствующий (и, вероятно, рекурсивный) метод - так,не могли бы вы дать эту недостающую спецификацию ...?

Редактировать : поскольку ОП уточнил, что, как и предсказывалось, стало легко удовлетворить спецификацию.Просто добавьте к class Node следующий метод:

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

и измените последние три строки кода (последнюю из makenest, пустую и вызов уровня модуля на makenest) to:

  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 3

Следите за текущей "глубиной", на которой вы анализируете.

• Если глубина следующей строки больше текущей глубины, рекурсивно вызвать синтаксический анализатор с новой глубиной, а затем добавить результат этого вызова в текущий список.
• Если глубина следующей строки равна текущей глубине, добавьте ее в текущий список.
• Если глубина следующей строки меньше текущей глубины, вернуть текущий список.