# COMP9021 Practice 9 - Solutions


'''
Evaluates an expression generated by the grammar:
                 EXPRESSION --> EXPRESSION TERM_OPERATOR TERM
                 EXPRESSION --> TERM
                 TERM --> TERM FACTOR_OPERATOR FACTOR
                 TERM --> FACTOR
                 FACTOR --> NUMBER
                 FACTOR --> (EXPRESSION)
                 NUMBER --> DIGIT NUMBER | DIGIT
                 DIGIT --> 0 | ... | 9
                 TERM_OPERATOR --> + | -
                 FACTOR_OPERATOR --> * | /
'''


import re
from functools import partial
from operator import add, sub, mul, truediv


def evaluate(expression):
    '''
    Checks whether an expression can be generated by the grammar,
    and in case the answer is yes, returns the value of the expression,
    and provided that no division by 0 is attempted; otherwise, return None.
    Note that all operators associate to the left.
    
    >>> evaluate('100') == eval('100')
    True
    >>> evaluate('(100)') == eval('(100)')
    True
    >>> evaluate('1 - 20 + 300') == eval('1 - 20 + 300')
    True
    >>> evaluate('(((((1))-((20))+((300)))))') == eval('(((((1))-((20))+((300)))))')
    True
    >>> evaluate('20 * 4 / 5') == eval('20 * 4 / 5')
    True
    >>> evaluate('(((((20))*((4))/((5)))))') == eval('(((((20))*((4))/((5)))))')
    True
    >>> evaluate('1 + 20 * 30 - 400 / 500') == eval('1 + 20 * 30 - 400 / 500')
    True
    >>> evaluate('1 + (20*30-400) / 500') == eval('1 + (20*30-400) / 500')
    True
    >>> evaluate('1+(20 / 30 * 400)- 500') == eval('1+(20 / 30 * 400)-500')
    True
    >>> evaluate('1 + 2 * (3+4*5) / (6*7-8/9)') == eval('1 + 2 * (3+4*5) / (6*7-8/9)')
    True
    >>> evaluate('100)')
    >>> evaluate('100 + ')
    >>> evaluate('100 + -3')
    >>> evaluate('100 ÷ 50')
    >>> evaluate('100 / 0')    
    '''
    if any(not (c.isdigit() or c.isspace() or c in '()+-*/') for c in expression):
        return
    # Tokens can be natural numbers, (, ), +, -, *, and /
    tokens = re.compile('(\d+|\(|\)|\+|-|\*|/)').findall(expression)
    tokens.reverse()
    try:
        value = evaluate_expression_or_term('+-', tokens)
        if len(tokens):
            return
        return value
    except ZeroDivisionError:
        return
    

def evaluate_expression_or_term(operators, tokens):
    evaluation_function = (partial(evaluate_expression_or_term, '*/')  if '+' in operators
                                                                       else evaluate_factor)
    value = evaluation_function(tokens)
    if value is None:
        return
    while len(tokens) and tokens[-1] in operators:
        operator = tokens.pop()
        other_value = evaluation_function(tokens)
        if other_value is None:
            return
        value = {'+': add, '-': sub, '*': mul, '/': truediv}[operator](value, other_value)
    return value


def evaluate_factor(tokens):
    try:
        token = tokens.pop()
        return int(token)
    # No token was left
    except IndexError:
        return
    except ValueError:
        if token != '(':
            return
        value = evaluate_expression_or_term('+-', tokens)
        if len(tokens) and tokens.pop() == ')':
            return value
        return


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


