import re
import math
import operator

def shunting_yard(exp):
    """ Converts expressions from infix to postfix notation

    >>> shunting_yard("5 + 6")
    ['5', '6', '+']
    >>> shunting_yard("9 + (5 * 2) + 3 / 4")
    ['9', '5', '2', '*', '+', '3', '4', '/', '+']

    Args:
        A string expression in infix notation

    Returns:
        A list expression in postfix notation

    """
    operator_precedence = {'+': 2, '-': 2,
                           '*': 3, '/': 3, '%' : 3,
                           '^': 4}
    operator_associativity = {'+': 'left', '-': 'left',
                              '*': 'left', '/': 'left', '%' : 'left',
                              '^': 'right'}
    valid_token = re.compile("[-]?[0-9]*\.[0-9]+|[-]?[0-9]+|[+-/^*()%]")
    valid_operator = re.compile("[+-/%*^]")
    valid_number = re.compile("[-]?[0-9]*\.[0-9]+|[0-9]+")

    exp = valid_token.findall(exp)
    output_queue = []
    operator_stack = []
    for token in exp:
        #Numbers can added to the queue in their original order
        if valid_number.search(token):
            output_queue.append(token)
        #Match only single characters that match the regex, e.g. not "-5"
        if valid_operator.search(token) and len(token) == 1:
            try: #Queue might be empty, will throw KeyError exception
                #Pop off operators and add them to the queue depending on
                #precedence and associativity.
                while (len(operator_stack) > 0 and
                       ((operator_associativity[token] == 'left' and
                         operator_precedence[token] <=
                         operator_precedence[operator_stack[-1]]) or
                        (operator_associativity[token] == 'right' and
                         operator_precedence[token] <
                         operator_precedence[operator_stack[-1]]))):
                    output_queue.append(operator_stack.pop())
            except KeyError:
                pass
            operator_stack.append(token)
            #Pop off operators inside parens until a closing paren is met
        if token == "(":
            operator_stack.append(token)
        if token == ")":
            while True:
                operator = operator_stack.pop()
                if operator == "(":
                    break
                else:
                    output_queue.append(operator)
        #Empty the stack if it is still full
    while len(operator_stack) > 0:
        output_queue.append(operator_stack.pop())
    return output_queue

def postfix_evaluator(exp):
    """ Evaluates postfix mathematical expressions

    >>> postfix_evaluator(["-5","3","8","+","*"])
    -55.0

    Args:
        A list expression in post-fix notation containing only

    Returns:
        The evaluation of the expression, as a float

    """

    op_dict = {'+': operator.add,
               '-': operator.sub,
               '*': operator.mul,
               '/': operator.truediv,
               '%': operator.mod,
               '^': math.pow}
    operand_stack = []

    valid_operator = re.compile("[+-/%*^]")
    valid_number = re.compile("[-]?[0-9]*\.[0-9]+|[0-9]+")
    #Place operands on the stack in the order they are encountered
    #When an operator is encountered, use it to operate on the last
    #two operands on the stack and push the result onto the stack
    for token in exp:
        if valid_number.search(token):
            operand_stack.append(token)
        if valid_operator.search(token) and len(token) == 1:
            operand2, operand1 = operand_stack.pop(), operand_stack.pop()
            operand_stack.append(op_dict[token](float(operand1),
                                                float(operand2)))
    return operand_stack.pop()

def evaluator(expression):
    """ Evaluates an infix-notated expression

    Args:
        A string expression in infix notation containing real numbers and
        operators (including +, -, *, /, %, and ^)

    Returns:
        The evaluation of the expression, as a float

    """
    return postfix_evaluator((shunting_yard(expression)))

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