import re
from collections import namedtuple
from fractions import Fraction
 
Token = namedtuple('Token', ['type', 'value'])
 
NUM_RE = r'(?P<NUM>\d+(\.\d*)?)'
WS_RE = r'(?P<WS>\s+)'
MUL_RE = r'(?P<MUL>\*)'
DIV_RE = r'(?P<DIV>/)'
PLUS_RE = r'(?P<PLUS>\+)'
MINUS_RE = r'(?P<MINUS>-)'
LPAREN = r'(?P<LPAREN>\()'
RPAREN = r'(?P<RPAREN>\))'
 
REGEXP = re.compile('|'.join([NUM_RE, WS_RE, MUL_RE, DIV_RE, PLUS_RE, MINUS_RE,
                             LPAREN, RPAREN]))
 
 
class Evaluator(object):
    def tokenize(self, s):
        scanner = REGEXP.scanner(s)
        for tok in iter(scanner.match, None):
            if tok.lastgroup != 'WS':  # skip whitespaces
                yield Token(tok.lastgroup, tok.group())
 
    def eval(self, s):
        self.tokens = self.tokenize(s)
        self.current_t = None
        self.next_t = None
        self.advance()
        return self.expr()
 
    def advance(self):
        self.current_t, self.next_t = self.next_t, next(self.tokens, None)
 
    def accept(self, tp):
        if self.next_t and self.next_t.type == tp:
            self.advance()
            return True
        else:
            return False
 
    def expect(self, tp):
        if not self.accept(tp):
            error_msg = "Expected {}, got {}".format(tp, self.next_t and self.next_t.value)
            raise SyntaxError(error_msg)
 
    def expr(self):
        left = self.term()
        while self.accept('PLUS') or self.accept('MINUS'):
            if self.current_t.type == 'PLUS':
                right = self.term()
                left += right
            else:
                right = self.term()
                left -= right
        return left
 
    def term(self):
        left = self.factor()
        while self.accept('MUL') or self.accept('DIV'):
            if self.current_t.type == 'MUL':
                left *= self.factor()
            else:
                left /= self.factor()
        return left
 
    def factor(self):
        if self.accept('MINUS') and self.accept('NUM'):
            return -1 * Fraction(self.current_t.value)
        elif self.accept('NUM'):
            return Fraction(self.current_t.value)
        else:
            self.expect('LPAREN')
            exp = self.expr()
            self.expect('RPAREN')
            return exp
 
 
# tests
def test():
    suit = {'2 + 2 * 2': 6,
            '(5 * 2) / 4': Fraction("5/2"),
            '1 + 1 + 1': 3,
            '3 * 4 / 2': 6,
            '-3 * (5 + 0)': -15,
            '3 * (5 + )': 15,
            '2.5 / -5': Fraction("-1/2")}
    ev = Evaluator()
    for expr, res in suit.iteritems():
        try:
            print "{} -> {}, expected {}".format(expr, ev.eval(expr), res)
        except SyntaxError as e:
            print "{} failed with: {}".format(expr, e)
 
if __name__ == '__main__':
    test()