'''Recursive Parser of Ariphmetic Formulas'''
import re
import math

# Lexeme types
NUMBER = 0
NAME = 1
PLUS = 2
MINUS = 3
MUL = 4
DIV = 5
POW = 6
LPAR = 7
RPAR = 8
X = 9
Y = 10
ENDLINE = 11
ILLEGAL = 12

regExpressions = [
    (r"[0-9]+(\.[0-9]*)?((e|E)(\+|\-)?[0-9]+)?", NUMBER),
    (r"[a-zA-Z][a-zA-Z0-9]*", NAME),
    (r"\+", PLUS),
    (r"\-", MINUS),
    (r"\^|(\*\*)", POW),
    (r"\*", MUL),
    (r"\/", DIV),
    (r"\(", LPAR),
    (r"\)", RPAR)
]

whiteSpace = re.compile(r"\s+")

# Table of standard functions (dictionary)
standardFunctions = {
    "sin": math.sin, "cos": math.cos, "exp": math.exp,
    "log": math.log, "sqrt": math.sqrt, "tan": math.tan, 
    "abs": math.fabs, "fabs": math.fabs, "atan": math.atan,
    "asin": math.asin, "acos": math.acos, "sinh": math.sinh, 
    "cosh": math.cosh, "tanh": math.tanh, "gamma": math.gamma,
    "erf": math.erf, "acosh": math.acosh, "asinh": math.asinh,
    "atanh": math.atanh
}

class Token:
    def __init__(self, lextype, text="", number=0.):
        self.lextype = lextype
        self.text = text
        self.number = number
        self.func = None

    def __str__(self):
        s = "("
        if self.lextype == NUMBER:
            s += "NUMBER"
        elif self.lextype == NAME:
            s += "NAME"
        elif self.lextype == PLUS:
            s += "PLUS"
        elif self.lextype == MINUS:
            s += "MINUS"
        elif self.lextype == MUL:
            s += "MUL"
        elif self.lextype == DIV:
            s += "DIV"
        elif self.lextype == POW:
            s += "POW"
        elif self.lextype == LPAR:
            s += "LPAR"
        elif self.lextype == RPAR:
            s += "RPAR"
        elif self.lextype == X:
            s += "X"
        elif self.lextype == Y:
            s += "Y"
        elif self.lextype == ENDLINE:
            s += "ENDLINE"
        elif self.lextype == ILLEGAL:
            s += "ILLEGAL"
        else:
            assert(False)
        s += ", \""
        s += self.text
        s += "\", "
        s += str(self.number)
        s += ")"
        return s

    def __repr__(self):
        return "Token" + str(self)

class ParserException(Exception):
    def __init__(self, text = "Parser error"):
        self.text = text

    def __str__(self):
        return self.text

    def __repr__(self):
        return str(self)

class Parser:
    def __init__(self):
        self.text = ""
        self.tokens = []
        self.textPos = 0
        self.tokensPos = 0
        self.rpn = []
        self.x = 0.
        self.y = 0.
        self.scannerRules = []
        self.compileScannerRules()
        self.stack = []
        self.compiled = False

    def compileScannerRules(self):
        self.scannerRules.clear()
        for (expr, lexType) in regExpressions:
            e = re.compile(expr)
            self.scannerRules.append((e, lexType))

    def setParseLine(self, text):
        self.text = text
        self.tokens.clear()
        self.textPos = 0
        self.tokensPos = 0
        self.rpn.clear()

    def scan(self):
        self.textPos = 0
        self.tokens.clear()
        self.tokensPos = 0
        textLen = len(self.text)
        while self.textPos < textLen:
            # Skip space
            m = whiteSpace.match(self.text[self.textPos:])
            if m != None:
                (lexBeg, lexEnd) = m.span()
                self.textPos += lexEnd
                continue

            ruleFound = False
            for (expr, lexType) in self.scannerRules:
                s = self.text[self.textPos:]
                m = expr.match(s)
                if m != None:
                    ruleFound = True
                    (lexBeg, lexEnd) = m.span()
                    assert(lexEnd - lexBeg > 0)
                    lexText = m.group()
                    t = Token(lexType, lexText)
                    if lexType == NAME:
                        if lexText == "x" or lexText == "X":
                            t.lextype = X
                        elif lexText == "y" or lexText == "Y":
                            t.lextype = Y
                        elif lexText == "pi" or lexText == "PI":
                            t.lextype = NUMBER
                            t.number = math.pi 
                        elif lexText == "e" or lexText == "E":
                            t.lextype = NUMBER
                            t.number = math.e 
                    elif lexType == NUMBER:
                        t.number = float(lexText)
                    self.tokens.append(t)
                    self.textPos += lexEnd - lexBeg
                    break

            if not ruleFound:
                break           # Illegal beginning of text

        self.tokens.append(Token(ENDLINE))

    #------------------------------------------------
    # Grammar rules:
    # S -> F $
    # F -> T | F + T | F - T
    # T -> M | T * M | T / M
    # M -> E | M ^ E
    # E -> Func | NUMBER | ( F )
    # Func -> NAME ( F )
    #------------------------------------------------
    # Transform the grammar to recursive form
    # S -> F ENDLINE
    # F -> T Ftail
    # Ftail -> + T Ftail | - T Ftail | empty
    # T -> M Ttail
    # Ttail -> * M Ttail | / M Ttail | empty
    # M -> E Mtail
    # Mtail -> ^ E Mtail | empty
    # E -> Func | NUMBER | ( F ) | X | Y
    # Func -> NAME ( F )
    #------------------------------------------------

    def parse(self):
        self.tokensPos = 0
        self.rpn.clear()
        try:
            self.processS()
            self.compiled = True
            return (True, "OK")
        except ParserException as e:
            self.compiled = False
            return (False, str(e))

    # S -> F ENDLINE
    def processS(self):
        if self.tokensPos >= len(self.tokens):
            raise ParserException("Empty formula")
        self.processF();
        self.skip(ENDLINE)
        
    def skip(self, lextype = (-1)):
        if self.tokensPos >= len(self.tokens):
            raise ParserException("Syntax error")
        if lextype >= 0:
            if self.tokens[self.tokensPos].lextype != lextype:
                raise ParserException("Syntax error")
        self.tokensPos += 1        
    
    # F -> T Ftail
    def processF(self):
        self.processT()
        self.processFtail()
        
    # Ftail -> + T Ftail | - T Ftail | empty
    def processFtail(self):
        if self.tokensPos >= len(self.tokens):
            return
        if self.tokens[self.tokensPos].lextype == PLUS:
            self.skip(PLUS)
            self.processT()
            self.rpn.append(Token(PLUS))        
            self.processFtail()
        elif self.tokens[self.tokensPos].lextype == MINUS:
            self.skip(MINUS)
            self.processT()
            self.rpn.append(Token(MINUS))        
            self.processFtail()
        
    # T -> M Ttail
    def processT(self):
        self.processM()
        self.processTtail()

    # Ttail -> * M Ttail | / M Ttail | empty
    def processTtail(self):
        if self.tokensPos >= len(self.tokens):
            return
        if self.tokens[self.tokensPos].lextype == MUL:
            self.skip(MUL)
            self.processM()
            self.rpn.append(Token(MUL))        
            self.processTtail()
        elif self.tokens[self.tokensPos].lextype == DIV:
            self.skip(DIV)
            self.processM()
            self.rpn.append(Token(DIV))        
            self.processTtail()

    # M -> E Mtail
    def processM(self):
        self.processE()
        self.processMtail()
        
    # Mtail -> ^ E Mtail | empty
    def processMtail(self):
        if self.tokensPos >= len(self.tokens):
            return
        if self.tokens[self.tokensPos].lextype == POW:
            self.skip(POW)
            self.processE()
            self.processMtail()
            self.rpn.append(Token(POW))        

    # E -> Func | NUMBER | ( F ) | X | Y
    def processE(self):
        if self.tokensPos >= len(self.tokens):
            raise ParserException("Syntax error")
            
        if self.tokens[self.tokensPos].lextype == NAME:
            self.processFunc()
        elif self.tokens[self.tokensPos].lextype == NUMBER:
            self.rpn.append(self.tokens[self.tokensPos])
            self.skip(NUMBER)
        elif self.tokens[self.tokensPos].lextype == LPAR:
            self.skip(LPAR)
            self.processF()
            self.skip(RPAR)
        elif self.tokens[self.tokensPos].lextype == X:
            self.rpn.append(self.tokens[self.tokensPos])
            self.skip(X)
        elif self.tokens[self.tokensPos].lextype == Y:
            self.rpn.append(self.tokens[self.tokensPos])
            self.skip(Y)
        else:
            raise ParserException("Syntax error")            
        
    # Func -> NAME ( F )
    def processFunc(self):
        if self.tokensPos >= len(self.tokens):
            raise ParserException("Syntax error")
            
        t = self.tokens[self.tokensPos] # Function name
        if t.text in standardFunctions:
            t.func = standardFunctions[t.text]
        self.skip(NAME)
        self.skip(LPAR)
        self.processF()
        self.skip(RPAR)
        self.rpn.append(t)              # Add the function call

    def compile(self):
        self.scan()
        (success, message) = self.parse()
        return (success, message)
        
    def evaluate(self, x = 0., y = 0.):
        self.stack.clear()
        for t in self.rpn:
            if t.lextype == NUMBER:
                self.stack.append(t.number)
            elif t.lextype == PLUS:
                b = self.stack.pop()
                a = self.stack.pop()
                self.stack.append(a + b)
            elif t.lextype == MINUS:
                b = self.stack.pop()
                a = self.stack.pop()
                self.stack.append(a - b)
            elif t.lextype == MUL:
                b = self.stack.pop()
                a = self.stack.pop()
                self.stack.append(a * b)
            elif t.lextype == DIV:
                b = self.stack.pop()
                a = self.stack.pop()
                self.stack.append(a / b)    
            elif t.lextype == POW:
                b = self.stack.pop()
                a = self.stack.pop()
                self.stack.append(a ** b)
            elif t.lextype == X:
                self.stack.append(x)
            elif t.lextype == Y:
                self.stack.append(y)
            elif t.lextype == NAME:
                a = self.stack.pop()
                res = 0.
                if t.func != None:
                    res = (t.func)(a)
                self.stack.append(res)
        return self.stack[0]                       
    
def main():
    parser = Parser()
    while True:
        vx = input("Enter the value of x: ")
        try:
            x = float(vx)
        except ValueError:
            break
        text = input("Enter an expression (\"q\" for the end):\n")
        if text == "q":
            break
        parser.setParseLine(text)
        (success, errorText) = parser.compile()
        if not success:
            print(errorText)
        try:
            v = parser.evaluate(x=x)
            print("=", v)
        except Exception as e:
            print(e)

if __name__ == "__main__":
    main()