Expression evaluator

evaluator.py

class Lexer(object):
    def __init__(self, s):
        self.s = s
        self.idx = 0
        self.token = None

    def peek(self):
        if self.idx >= len(self.s):
            return None
        else:
            return self.s[self.idx]

    def next(self):
        if self.idx >= len(self.s):
            raise IndexError
        ch = self.s[self.idx]
        self.idx += 1
        return ch

    def lex(self):
        if self.peek() is None:
            return None
        else:
            ch = self.next()
            if ch in ' \t\r\n':
                return self.lex()
            elif ch in '1234567890':
                return self.lex_num(int(ch))
            elif ch in '+-*/^()':
                return ch
            else:
                raise ValueError("invalid character")

    def lex_num(self, x):
        ch = self.peek()
        while ch is not None and ch in '0123456789':
            x = x * 10 + int(ch)
            self.next()
            ch = self.peek()
        return x

    def peek_token(self):
        if self.token is None:
            self.token = self.lex()
        return self.token

    def next_token(self):
        if self.token is None:
            return self.lex()
        else:
            tok = self.token
            self.token = None
            return tok


# expr   ::= term ((+|-) term)*
# term   ::= expo ((*|/) expo)*
# expo   ::= factor (^ expo)?
# factor ::= unary | '(' expr ')'
# unary  ::= (+|-) unary | int
class Evaluator(object):
    """
    >>> Evaluator.eval('1')
    1
    >>> Evaluator.eval('2 + 3')
    5
    >>> Evaluator.eval('2 * 3')
    6
    >>> Evaluator.eval('1 + 2 * 3')
    7
    >>> Evaluator.eval('(1 + 2) * 3')
    9
    >>> Evaluator.eval('13 * -4 + ---6')
    -58
    >>> Evaluator.eval('(2 ^ 3) ^ 4')
    4096
    >>> Evaluator.eval('2 ^ 3 ^ 4')
    2417851639229258349412352L
    """
    @classmethod
    def eval(cls, s):
        lexer = Lexer(s)
        x = cls.expr(lexer)
        # ensure EOS
        if lexer.peek_token() is not None:
            raise ValueError("syntax error")
        return x

    @classmethod
    def expr(cls, lexer):
        x = cls.term(lexer)
        op = lexer.peek_token()
        while isinstance(op, str) and op in '+-':
            # discard OP
            lexer.next_token()
            y = cls.term(lexer)
            if op == '+':
                x += y
            else:
                x -= y
            op = lexer.peek_token()
        return x

    @classmethod
    def term(cls, lexer):
        x = cls.expo(lexer)
        op = lexer.peek_token()
        while isinstance(op, str) and op in '*/':
            # discard OP
            lexer.next_token()
            y = cls.expo(lexer)
            if op == '*':
                x *= y
            else:
                x /= y
            op = lexer.peek_token()
        return x

    @classmethod
    def expo(cls, lexer):
        x = cls.factor(lexer)
        if lexer.peek_token() == '^':
            # pop out '^'
            lexer.next_token()
            y = cls.expo(lexer)
            return x ** y
        else:
            return x

    @classmethod
    def factor(cls, lexer):
        tok = lexer.peek_token()
        if tok == '(':
            # discard LPAREN
            lexer.next_token()
            x = cls.expr(lexer)
            # discard RPAREN
            cls.eat(lexer, ')')
            return x
        else:
            return cls.unary(lexer)

    @classmethod
    def unary(cls, lexer):
        tok = lexer.peek_token()
        if tok == '+':
            lexer.next_token()
            return cls.unary(lexer)
        elif tok == '-':
            lexer.next_token()
            x = cls.unary(lexer)
            return -x
        elif isinstance(tok, int):
            lexer.next_token()
            return tok

    @classmethod
    def eat(cls, lexer, tok):
        if lexer.peek_token() != tok:
            raise ValueError("syntax error")
        else:
            # eat token
            lexer.next_token()


if __name__ == '__main__':
    import doctest
    doctest.testmod()