Arithmetic expression parser coding challenge

interview coding challenge - arithmetic expression evaluator

#
# Coding challenge that took me well over an hour for a one-hour limi.
# I started by overbuilding.   Lesson learned is - do minimum viable
# for interview coding challenges!
#
# Sigh.
#
# Challenge is to parse a string representing an arithmetic expression
# and evaluate it without using eval()
#
# String consists of integers and the operations +, -, *, /
# No unary ops
# No higher precedence ops ( exponentiation )
# No parentheses
# 
# Afterward I realized the solution was really about sticking
# with the assumptions and not coding anything beyond them:
#
#  . String is alternating ints and ops, delimited by a single space.
#     - tokenize really just means string split
#     - every op is followed by an int
#     - every int is followed by an op or by some implied "End" token
#  . String always starts with an int and ends with an int
#     - every time we see an op we can assume there's and int after it
#  . String contains no errors
#      - don't write input validations
#  
# And of course, there are no parens, no exponents, etc etc.
#
# I started off building a nice little parser, returning token objects
# with a value and token_type.  Really dumb in retrospect.  Clearly the
# challenge was meant to assess ability to scope a project and avoid
# overbuilding.
#
# Lessons learned.
#


class Evaluator:

    def __init__(self, text):
        self.tokens = text.split(' ') + [ None ] # Use 'None' as the end token
        self.idx = 0;
        self.maxidx = len(self.tokens) - 1

    def next(self):

        if self.tokens[self.idx] == None:
            return None
        self.idx = self.idx + 1
        return self.tokens[ self.idx ]

    def current(self):
        return self.tokens[ self.idx ]

    def term( self, advance = False ):

        left = int( advance and self.next() or self.current() )
        op = self.next()

        if op == '*': return left * self.term(True)
        if op == '/': return left / self.term(True)
        return left

    def expr( self ):

        left = self.term()

        while True:
            op = self.current()
            if op == None: return left
            if op == '+': left = left + self.term(True)
            elif op == '-': left = left - self.term(True)


def evaluate( text ):
    return Evaluator(text).expr()


TESTS = [

    {
        'text': '1 * 2 * 3 * 4',
        'expect': 24
    },
    { 
        'text': '1 + 2',
        'expect':  3
    } ,
    { 
        'text': '1 + 2 + 3',
        'expect': 6
    },
    { 
        'text': '1 + 2 * 3 + 4',
        'expect': 11
    },
    { 
        'text': '2 * 2 - 3 * 4',
        'expect': -8
    },
    { 
        'text': '2 * 2 + 3 * 4',
        'expect': 16
    },
    { 
        'text': '2 * 2 * 2 + 3 * 4 - 10',
        'expect': 10
    },
    { 
        'text': '1 + 2 * 2 * 2 + 3 * 4 - 10',
        'expect': 11
    },
    { 
        'text': '1 + 2 * 2 * 2 + 3 * 4 - 10 - 1',
        'expect': 10
    },
    { 
        'text': '2 + 3 - 10 - 1',
        'expect': -6
    }
]

for test in TESTS:
    result = evaluate( test['text'] )
    if result == test['expect']:
       print("PASS {0} = {1}".format( test['text'], result ))
    else:
       print("FAIL {0} : {1} != expected {2}".format( test['text'], result, test['expect'] ))