Tokenizing blocks of code in Python

Question

I have this string:

[a [a b] [c e f] d]

and I want a list like this

lst[0] = "a"
lst[1] = "a b"
lst[2] = "c e f"
lst[3] = "d"

My current implementation that I don't think is elegant/pythonic is two recursive functions (one splitting with '[' and the other with ']' ) but I am sure it can be done using list comprehensions or regular expressions (but I can't figure out a sane way to do it).

Any ideas?

Answer 1

Well, if it's a recursive data structure you're going to need a recursive function to cleanly navigate it.

But Python does have a tokenizer library which might be useful: http://docs.python.org/library/tokenize.html

Answer 2

Actually this really isn't a recursive data structure, note that a and d are in separate lists. You're just splitting the string over the bracket characters and getting rid of some white space.

I'm sure somebody can find something cleaner, but if you want a one-liner something like the following should get you close:

parse_str = '[a [a b] [c e f] d]'
lst = [s.strip() for s in re.split('[\[\]]', parse_str) if s.strip()]

>>>lst
['a', 'a b', 'c e f', 'd']

Answer 3

If it's a recursive data structure, then recursion is good to traverse it. However, parsing the string to create the structure does not need to be recursive. One alternative way I would do it is iterative:

origString = "[a [a b] [c [x z] d e] f]".split(" ")
stack = []
for element in origString:
    if element[0] == "[":
        newLevel = [ element[1:] ]
        stack.append(newLevel)
    elif element[-1] == "]":
        stack[-1].append(element[0:-1])
        finished = stack.pop()
        if len(stack) != 0:
            stack[-1].append(finished)
        else:
            root = finished
    else:
        stack[-1].append(element)
print root

Of course, this can probably be improved, and it will create lists of lists of lists of ... of strings, which isn't exactly what your example wanted. However, it does handle arbitrary depth of the tree.