Parse Math Expression

parse_math_expression.py

# Simple Shunting-Yard solution
#
# Given a math expression, parse and evaluate
# the expression
#
# E.g '2+1' => 3, 8/2*4+1 => 17, 2+(1*2) = 4, ((2+4)/2*7) => 21
# 
def parse_math_expression(exp):
    PRECENDENCE = {
        ')': 3,
        '(': 3,
        '*': 1,
        '/': 1,
        '+': 0,
        '-': 0,
    }
    output = []
    operators = []
    for ch in exp:
        # Handle nested expressions
        if ch == ')':
            opr = operators.pop(0)
            while opr != '(':
                output.append(opr)
                opr = operators.pop(0)
        elif ch.isdigit():
            output.append(ch)
        else:
            # Handle operator prescendence
            top_op = len(operators) and operators[0]
            # Check if top operator has greater prcendencethan current char
            if top_op in ['*', '/'] and PRECENDENCE[top_op] > PRECENDENCE[ch]:
                output.append(top_op)
                operators.pop(0)
            # Push operator onto queues
            operators.insert(0, ch)
    # Handle any leftover operators
    while len(operators):
        output.append(operators.pop(0))
    return output

test1 = "(2+1)"
assert parse_math_expression(test1) == ['2', '1', '+']
test2 = "((2+4)/(2*7))"
assert parse_math_expression(test2) == ['2', '4', '+', '2', '7', '*', '/']
test3 = "(3*2)+(4/2)"
assert parse_math_expression(test3) == ['3', '2', '*','4', '2', '/','+']

def eval_parsed_expression(exp):
    OPRS = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: a / b
    }
    tmp = []
    while len(exp) > 1:
        k = exp.pop(0)
        while not k in ['*', '-', '+', '/']:
            tmp.insert(0, k)
            k = exp.pop(0)
        o = k
        b = tmp.pop(0)
        a = tmp.pop(0)
        r = OPRS[o](int(a), int(b))
        exp.insert(0, r)
    return exp[0]

test4 = ['2', '1', '+'] # (2+1*2)
assert eval_parsed_expression(test4) == 3
test5 = ['2', '1', '2', '*', '+'] # (2+1*2)
assert eval_parsed_expression(test5) == 4
test6 = ['3', '2', '*','4', '2', '/','+'] # (3*2)+(4/2)
assert eval_parsed_expression(test6) == 8