How do I process a nested list?

Posted by ddbeck on Stack Overflow See other posts from Stack Overflow or by ddbeck
Published on 2010-06-06T03:19:36Z Indexed on 2010/06/06 3:22 UTC
Read the original article Hit count: 375

Filed under:
|
|

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):

[('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?

© Stack Overflow or respective owner

Related posts about python

Related posts about parsing