Limited Lisp parser for RC pairing interview

parser.py

# Represents a valid Lisp expression. Here, the only
# valid 'core' type is a floating point number.
# Note that this 'version' of Lisp does _not_ support
# empty lists; that is, every list must have an explicit
# operator, even if that operator is "list".


class LispExpression:
    def __init__(self, src):
        cleaned = LispExpression.clean(src)
        composed = LispExpression.compose(cleaned)
        self.ast = composed

    # Converts a variably-spaced input string into a
    # uniformly-spaced new string -- that is, there is
    # a space between all "components" (including parenthesis).
    @staticmethod
    def clean(src):
        src = src.replace("(", " ( ")
        src = src.replace(")", " ) ")
        while "  " in src:
            src = src.replace("  ", " ")
        src = src.strip()
        return src

    # Turn a uniformly-spaced input string into an abstract
    # syntax tree (AST) representation. This function
    # enforces valid syntax trees, but does not enforce
    # valid and "evaluatable" expressions.
    @staticmethod
    def compose(src):
        stack = []  # the last item is the 'current list'
        components = src.split(" ")
        for i in range(len(components)):  # iterating by index instead of value because
                                          # we will want to ensure we reach the end
                                          # of the stack by the final closing
                                          # parenthesis
            component = components[i]
            if component == "(":
                stack.append([])  # opening parenthesis means 'new list'
            elif component == ")":
                group = stack.pop()  # current list is finished; pop it off the stack
                if len(stack) == 0:  # if true, then we have reached the end of the 'original' list
                    if i != len(components) - 1:
                        # freak out because the original list is closed but there is more to go
                        raise Exception(
                            "invalid expression: unexpectedly reached terminating parenthesis before components end")
                    return group  # happily return closed list
                else:
                    # add the finished list as an item to the outer list
                    stack[-1].append(group)
            else:
                if len(stack) == 0:  # found non-parenthesis outside of list
                    raise Exception(
                        "invalid expression: found value outside of list (`%s`)" % component)
                try:  # try to convert component to a number
                    component = float(component)
                except:
                    pass
                # append component to current working list
                stack[-1].append(component)
        raise Exception(
            "invalid expression: missing opening/closing delimeters or contents")

    def tree(self):
        return self.ast

    # Evaluate the expression and return a final value (be it a list or a number)
    def evaluate(self):
        raise NotImplementedError()


# A few test cases to ensure _most things_ are in working order
assert LispExpression(
    "(first (list 1 (+ 2 3) 9))").tree() == ["first", ["list", 1, ["+", 2, 3], 9]]
assert LispExpression("()").tree() == []
assert LispExpression("(((hello)))").tree() == [[["hello"]]]
assert LispExpression("(1 2(3 4)5)").tree() == [1, 2, [3, 4], 5]
assert LispExpression("((((()))))").tree() == [[[[[]]]]]
assert LispExpression("(1        2    3    4  5 (6))").tree() == [
    1, 2, 3, 4, 5, [6]]