如何处理嵌套列表? [英] How do I process a nested list?

问题描述

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

* 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. 我敢肯定我不是第一个这样做的人，但是我不知道问题的术语，无法对有关此主题的更多信息进行富有成效的搜索.与此相关的问题是什么，这样我就可以总体上了解有关解决这类问题的更多信息?

解决方案

我无法解析您想要的结果-它似乎比对应的封闭括号具有更多的开放括号，并且我不了解其背后的逻辑. /p>

要使树形结构清晰可见，例如:

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

Suppose I have a bulleted list like this:

* 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

I'd like to parse that into a nested list or some other data structure which makes the parent-child relationship between elements explicit (rather than depending on their contents and relative position). For example, here's a list of tuples containing an item and a list of its children (and so forth):

Edit: Hopefully, a more correct list example, where each element in the list is a tuple containing: a bullet's text and, if applicable, a list of children (in the same form).

    [('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',)]

I've attempted to do this with plain Python and some experimentation with Pyparsing, but I'm not making progress. I'm left with two major questions:

1. What's the strategy I need to employ to make this work? I know recursion is part of the solution, but I'm having a hard time making the connection between this and, say, a Fibonacci sequence.
2. I'm certain I'm not the first person to have done this, but I don't know the terminology of the problem to make fruitful searches for more information on this topic. What problems are related to this so that I can learn more about solving these kinds of problems in general?

解决方案

I can't parse your desired result -- it seems to have more open parentheses than corresponding closed ones and I don't understand the logic behind it.

To make a tree structure explicit, what about, e.g.:

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)

The show method of course exists just for the purpose of verifying that the part about parsing the strings and creating the tree has worked correctly. If you can specify more precisely exactly how it is that you want to transform your tree into nested tuples and lists, I'm sure it will be easy to add to class Node the appropriate (and probably recursive) method -- so, could you please give this missing specification...?

Edit: since the OP has clarified now, it does, as predicted, become easy to satisfy the spec. Just add to class Node the following method:

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

and change the last three lines of the code (last one of makenest, a blank one, and the module-level call to makenest) to:

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

print(makenest(data))

(The parentheses after print are redundant but innocuous in Python 2, required in Python 3, so I put them there just in case;-).

With these tiny changes, my code runs as requested, now emitting

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

这篇关于如何处理嵌套列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！