## Begin parser
from string import *
from yapps import SyntaxError, NoMoreTokens
from yapps import Scanner

class CalculatorScanner(Scanner):
    def __init__(self, str):
        Scanner.__init__(self,[
            ('")"', ')'),
            ('"("', '('),
            ('"/"', '/'),
            ('"*"', '*'),
            ('"-"', '-'),
            ('"+"', '+'),
            ('END', '$'),
            ('NUM', '[0-9]+'),
            ], [], str)

class Calculator:
    def __init__(self, scanner):
        self.scanner = scanner

    def token(self, _pos_, type):
        tok = self.scanner.token(_pos_)
        if tok[2] != type:
            raise SyntaxError(tok[0], 'Trying to find '+type)
        return tok[3]

    def expr_tail(self,_pos_, v):
        while 1:
            _start_,_,_token_,_text_ = self.scanner.token(_pos_)
            if _token_ in ['END', '")"']:
                return v, _pos_
            elif _token_ == '"+"':
                factor,_pos_ = self.factor(1+_pos_)
                v = v+factor
            elif _token_ == '"-"':
                factor,_pos_ = self.factor(1+_pos_)
                v = v-factor
            else:
                raise SyntaxError(_start_, 'Could not match expr_tail')

    def factor(self,_pos_=0):
        _start_,_,_token_,_text_ = self.scanner.token(_pos_)
        term,_pos_ = self.term(_pos_)
        return self.factor_tail(_pos_, term)

    def goal(self,_pos_=0):
        _start_,_,_token_,_text_ = self.scanner.token(_pos_)
        expr,_pos_ = self.expr(_pos_)
        self.token(_pos_,'END')
        return expr, 1+_pos_

    def factor_tail(self,_pos_, v):
        while 1:
            _start_,_,_token_,_text_ = self.scanner.token(_pos_)
            if _token_ in ['"+"', '"-"', 'END', '")"']:
                return v, _pos_
            elif _token_ == '"*"':
                term,_pos_ = self.term(1+_pos_)
                v = v*term
            elif _token_ == '"/"':
                term,_pos_ = self.term(1+_pos_)
                v = v/term
            else:
                raise SyntaxError(_start_, 'Could not match factor_tail')

    def term(self,_pos_=0):
        _start_,_,_token_,_text_ = self.scanner.token(_pos_)
        if _token_ == 'NUM':
            NUM = _text_
            return (atoi(NUM)), 1+_pos_
        elif _token_ == '"("':
            expr,_pos_ = self.expr(1+_pos_)
            self.token(_pos_,'")"')
            return expr, 1+_pos_
        else:
            raise SyntaxError(_start_, 'Could not match term')

    def expr(self,_pos_=0):
        _start_,_,_token_,_text_ = self.scanner.token(_pos_)
        factor,_pos_ = self.factor(_pos_)
        return self.expr_tail(_pos_, factor)

def parse(rule, input):
    parser = Calculator(CalculatorScanner(input))
    try: return getattr(parser, rule)()[0]
    except SyntaxError, s:
        try:
            from yapps import print_error
            print_error(input, s, parser.scanner)
        except ImportError:
            print 'Syntax Error',s.msg,'on line',1+count(input[:s.pos], '\n')
    except NoMoreTokens:
        print 'Ran out of input'