#!/usr/bin/env python
# -*- coding: utf-8 -*-

from operator import *
from collections import namedtuple
from functools import reduce
import re, string, math

Op = namedtuple('Op', 'fun arity prec left_assoc')
Const = namedtuple('Const', 'val')
Fun = namedtuple('Fun', 'fun arity')
Par = namedtuple('Par', 'val')
Comma = namedtuple('Comma', '')
Token = namedtuple('Token', 'type val')

funs = { 'max': Fun(max, 2),
         'min': Fun(min, 2),
         'ceil': Fun(math.ceil, 1),
         'floor': Fun(math.floor, 1),
         'log': Fun(math.log, 2),
         'exp': Fun(math.exp, 2),
         'complex': Fun(lambda x, y: x + y * 1j, 2) }

consts = { 'pi': Const(math.pi),
           'e': Const(math.e) }

#ops shouldn't not contain any 'Z' see definition of pattern in tokenize (yes it sucks)
ops = { '**': Op(pow, 2, 10000, False),
        '//': Op(floordiv, 2, 100, True),
        '.-': Op(neg, 1, 1000, False),
        '-': Op(sub, 2, 10, True),
        '*': Op(mul, 2, 100, True),
        '+': Op(add, 2, 10, True),
        '/': Op(truediv, 2, 100, True),
        '%': Op(mod, 2, 100, True),
        '~': Op(invert, 1, 1000, False),
        '<<': Op(lshift, 2, 9, True),
        '>>': Op(rshift, 2, 9, True),
        '&': Op(and_, 2, 8, True),
        '^': Op(xor, 2, 7, True),
        '|': Op(or_, 2, 6, True),
        'not': Op(not_, 1, 5, True),
        '<': Op(lt, 2, 5, True),
        '<=': Op(le, 2, 5, True),
        '>': Op(gt, 2, 5, True),
        '>=': Op(ge, 2, 5, True),
        '!=': Op(ne, 2, 5, True),
        '==': Op(eq, 2, 5, True),
        'and': Op(lambda x, y: bool(x and y), 2, 4, True),
        'or': Op(lambda x, y: bool(x or y), 2, 3, True),
        '!': Op(lambda x: reduce(mul, list(range(1, x + 1))), 1, 100000, True) }

def tokenize(exp):
    """
        Return exp as a list of tokens
    """
    o = list(ops.keys())
    o.sort()
    o.reverse() #pour avoir les doubles ops avant les simples
    pattern = r'\d+\.?\d*|\.\d+|[()]|' + '|'.join(funs) + '|' + '|'.join(consts) + '|' + re.escape('Z'.join(o)).replace('Z', '|')
    
    exp = exp.replace(string.whitespace, '')

    if exp == '':
        raise Exception('Empty expression.')

    tokens = re.findall(pattern, exp)

    for e in tokens:
        if re.match(r'^\d+$', e):
            yield Token(Const, Const(int(e)))
        elif re.findall(r'\d+\.?\d*|\.\d+', e):
            yield Token(Const, Const(float(e)))
        elif e in consts:
            yield Token(Const, consts[e])
        elif e in funs:
            yield Token(Fun, funs[e])
        elif e == ',':
            yield Token(Comma, Comma())
        elif e in '()':
            yield Token(Par, Par(e))
        elif e in ops:
            yield Token(Op, ops[e])
        else:
            raise Exception('Unknown operator: ' + e + '.')

def shunting_yard(exp):
    """
        Apply the shunting-yard algorithm to exp, it transform an infix
        expression to a postfix one
    """
    out, stack = [], []
    for token in tokenize(exp):
        if token.type == Const:
            out.append(token)
        elif token.type == Fun:
            stack.append(token)
        elif token.type == Comma:
            while stack != [] and stack[-1].type != Par: #we never add ')' to the stack...
                out.append(stack.pop())

            if stack == []:
                raise Exception('Misplaced separator, or mismatched parentheses.')
        elif token.type == Op:
            o1 = token.val

            while stack != [] and stack[-1].type == Op:
                o2 = stack[-1].val

                if (o1.left_assoc and o1.prec <= o2.prec) or (not o1.left_assoc and o1.prec < o2.prec):
                    out.append(stack.pop())
                else:
                    break
            stack.append(token)
        elif token.type == Par:
            if token.val.val == '(':
                stack.append(token)
            else:
                while stack != [] and stack[-1].type == Op:
                    out.append(stack.pop())
                if stack == [] or stack[-1].type != Par:
                    raise Exception('Mismatched parentheses.')
                
                stack.pop()

                if stack != [] and stack[-1].type == Fun:
                    out.append(stack.pop())

    while stack != []:
        if stack[-1].type == Par:
            raise Exception('Mismatched parentheses.')
        out.append(stack.pop())

    return out

def rpn(out):
    """
        Evaluate the rpn
    """
    v = []

    for i in out:
        if i.type == Const:
            v.append(i)
        elif i.val.arity == 0:
            v.append(Token(Const, Const(i.val.fun())))
        elif i.val.arity <= len(v):
            args = v[-i.val.arity:]
            v = v[0:-i.val.arity]
            v.append(Token(Const, Const(
                            i.val.fun(
                                *(list(map(lambda x: x.val.val, args)))
                                )
                            )))
        else:
            raise Exception('Not enough args.')
    
    if len(v) != 1:
        raise Exception('Hummm strange problem.')

    return v[0].val.val

def calc(exp):
    """
        Evaluate an exp, for instance if exp = 3 * (2 + 4), the function will
        return 18.
    """
    try:
        return rpn(shunting_yard(exp))
    except:
        raise

#(1 / max(max(1, 12), max(23, 3))) * ((4 * 5) - 6) * (78 - 9) * (ceil(pi) // floor(pi))
#(1<<1)*(2^1)*((3!*2+3)&~.-2**3)
exp = ''
while True:
    print('Enter an expression to evaluate (type quit to quit!): ', end = '')
    exp = input()

    if exp == 'quit':
        break
    try:
        print('The answer is:', calc(exp))
    except Exception as e:
        print('Sorry there is an error in your expression:')
        print(e)