0

I need to be able to take lists containing strings and nested lists of strings like the following:

['parent', ['child', 'child2', ['grandchild', ['ggrandchild'], 'grandchild2'], 'child3'], '2parent', '3parent' ['3child', ['3grandchild']]]

And print strings for each parent, each parent-child, each parent-child-grandchild, etc.:

'parent'
'parent_child'
'parent_child2'
'parent_child2_grandchild'
'parent_child2_grandchild_ggrandchild'
'parent_child2_grandchild2'
'parent_child3"
'2parent'
...
etc

I have been able to get it to work to a depth of two nested levels with the following code:

def list_check(parsed_list):
    for item in parsed_list:

        if type(item) != list and prefix == []: 
            prefix.append(str(item))
            print item

        elif type(item) != list and prefix != []: 
            print prefix[0]+"-"+item

        elif type(item) == list:
            list_check(item)

        else:
            pass

But I'm struggling with getting it to work for arbitrary nesting depth. I've taken a basic approach of tracking the nesting depth through a stack, but my implementation is broken in an obvious way that I don't know how to fix.

It currently deletes what is in the stack even if there are still other children following. What I want it to do is only pop items out of the relevant stacks if the sublist is ending.

prefix = []
nesting_depth = []

def list_check(parsed_list):
    for item in parsed_list:

        if type(item) == list:

            nesting_depth.append('1')
            list_check(item)

        elif type(item) != list and prefix == []: 
            prefix.append(str(item))
            print item

        elif type(item) != list and prefix != []: #this where i need another condition like 'and item is last in current sublist'
            print prefix[0:len(nesting_depth)]+"-"+item
            prefix.pop()

        else:
            pass

How do I reference something like 'if it's the last item in the current sublist of parsed_list' in a way that accommodates the recursion of the overall function?

2 Answers 2

2

A dictionary would be much better suited to your needs. But here's what you can do with the data structure you have:

def format_tree(tree):                                                                                            
    prefix = ''
    for node in tree:
        if isinstance(node, basestring):
            prefix = node
            yield node
        else:
            for elt in format_tree(node):
                yield prefix + '_' + elt 

A simple test:

>>> a = ['parent', ['child', 'child2', ['grandchild', ['ggrandchild']], 'child3']]
>>> print '\n'.join(format_tree(a))
parent
parent_child
parent_child2
parent_child2_grandchild
parent_child2_grandchild_ggrandchild
parent_child3
4
  • In trying to run your test, I'm getting the exception, "global name 'subtree' not defined." I'm sure there's something simple I'm not understanding.
    – Charles W
    Commented Apr 25, 2012 at 1:32
  • 1
    Sorry, error on my end when simplifying the code. The updated code should work.
    – Mzzzzzz
    Commented Apr 25, 2012 at 2:01
  • Great - thank you for the help. I'm going to look into using dicts for stuff like this in the future, but for now, it's nice to have something that works with what I've got.
    – Charles W
    Commented Apr 25, 2012 at 2:20
  • Having done some research on dictionaries, I'm confused about something with regard to this application. Namely, my data is going to have repeated values. Will that be a problem if using a dict since you cannot reuse keys?
    – Charles W
    Commented Apr 25, 2012 at 14:01
1
  1. You should pass in the path from the root node as an extra argument in the recursion.
  2. You are using the wrong datastructure; you want to be using dictionaries.

Example:

>>> tree = {1:{11:'a', 12:'b'}, 2:{22:'c'}}
>>> def visit(tree, path=[]):
...     if isinstance(tree, dict):
...         for node,subtree in tree.items():
...             visit(subtree, path=path+[node])
...     else:
...         leaf = tree
...         print(path, leaf)

>>> visit(tree)
[1, 11] a
[1, 12] b
[2, 22] c
1
  • Having done some research on dictionaries, I'm confused about something with regard to this application. Namely, my data is going to have repeated values. Will that be a problem if using a dict since you cannot reuse keys?
    – Charles W
    Commented Apr 25, 2012 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.