How to make a new List when you see a "(" and close it using ")". Lisp to Python

Question

I want to make a Lisp interpreter and I am just struggling on translating it after tokenizing it. So after Tokenizing it the list I have looks something like this.

tokenized = ["(", "car", "'","(", "20", "40", "60", ")", ")"] 

What I want is to Translate it in to something that looks like this

translated = [["CAR", "'", [20, 40, 60]]]

I need to a way to make a new list when it sees "(" and closes it when it sees ")". Let me know if I need to explain it better, I am terrible at explaining.

Answer 1

Ok, so this works like a recursive descent parser. Every time it sees an open bracket, it creates a new list, appends that to the output list and recurses down, but with the new list. Every time it sees a close bracket, it just returns to where it was before. The base case to recursion is reaching the end of the items to parse:

def rdp(items):
    it = iter(items)
    def inner(it, out):
        while True:
            token = next(it)
            if token == '(':
                nxt = []
                out.append(nxt)
                inner(it, nxt)
                continue
            elif token == ')':
                return
            out.append(token)

    nxt = []
    try:
        inner(it, nxt)
    except StopIteration:
        pass
    return nxt

tokenized = ["(", "car", "'","(", "20", "40", "60", ")", ")"]
translated = rdp(tokenized)

Output as requested

Note: I've just edited it to move the try:except: outside of the inner() recursive function to avoid repeated exceptions.