Iterating nested list inside-out

Question

I have the following python nested list structure:

test = ['a', ['c', ['e'], 'd'], 'b']

or the same, just formatted:

test = [
    'a', 
        [
            'c', 
                [
                    'e'
                ], 
             'd'
        ], 
    'b'
]

I was wondering what the best way would be to iterate over the complete list, starting with the innermost nested list object ('e') to the outermost list ('a', [...], 'b') in reversed order. A call to reversed(test) just doesn't do the trick with nested lists. And it should be able invoke a callback function on every depth of the iteration.

The iterations should look something like this ([xx] == computed value from previously invoked callback):

1st e --> callback(e)
2nd c [e] d --> callback(c [e] d)
3rd a [c e d] b --> callback(a [c e d] b)

Hope this explains my problem & thanks for your help

Answer 1

What you are looking for is a postorder traversal of the structure:

def traverse(l):
    for x in l:
        if isinstance(x, list):
            traverse(x)
    callback(l)

If callback is defined as print, we get

['e']
['c', ['e'], 'd']
['a', ['c', ['e'], 'd'], 'b']

Answer 2

One possible solution I would propose is

>>> def foo(test):
    queue = []
    try:
        while True:
            queue.append(test)
            test = test[1]
    except IndexError:
        for e in reversed(queue):
            yield e


>>> data = foo(test)
>>> next(data)
['e']
>>> next(data)
['c', ['e'], 'd']
>>> next(data)
['a', ['c', ['e'], 'd'], 'b']
>>> next(data)

Traceback (most recent call last):
  File "<pyshell#753>", line 1, in <module>
    next(data)
StopIteration
>>> 

How it works

1. Traverse depth-first, and push the elements in a queue
2. Loop through the reversed queue and yield the elements