import re
# inspired by:
# https://en.wikipedia.org/wiki/Reverse_Polish_notation
# https://en.wikipedia.org/wiki/Shunting-yard_algorithm

tests = [
    '12 + 2 * 10 -11 * 2 / 1', # 10
    '2 * 3 + 6 / 2', # 9
    '(1+2)*3',
    '1*(1+2*3)*4',
    '(2-(4+8*3))-9',
    '((1-2)+3)', # broken
    '(((3-1)))',
    '((3-1)+(3-1))'
]

OPS = ('+', '-', '*', '/', '(', ')')
OP_LEVEL = { '+': 1, '-': 1, '*': 2, '/': 2, '(': 3, ')': 3 }

def op_helper(j, i, op):
    if (op == '+'):
        return i+j
    elif (op == '-'):
        return i-j
    elif (op == '*'):
        return i*j
    elif (op == '/'):
        return i/j

def string_to_arr(expr):
    expr = expr.replace(' ', '')
    store = []
    tmp = []
    for x in expr:
        if x in OPS:
            if tmp:
                store.append(int(''.join(tmp)))
            store.append(x)
            tmp = []
        else:
            tmp.append(x)
    else:
        if tmp:
            store.append(int(''.join(tmp)))

    return store


def transform_to_reverse_polish(expr):
    expr = string_to_arr(expr)

    tokens = []
    output = []

    for ele in expr:
        if ele in OPS:
            # print 'output', output
            # print 'tokens', tokens
            if not tokens:
                tokens.append(ele)
                continue

            last_op = tokens[-1]

            if OP_LEVEL[ele] > OP_LEVEL[last_op]:  # [+] <- '*'
                tokens.append(ele)
                if ele == ')': # pop tokens until encounter with '('
                    tokens.pop()
                    while(tokens):
                        t = tokens.pop()
                        if t != '(':
                            output.append(t)
                        else: # t == '('
                            break

            elif OP_LEVEL[ele] == OP_LEVEL[last_op]: # [+ *] <- '/''
                if ele == '(':
                    tokens.append(ele)
                elif ele == ')':
                    while(tokens):
                        t = tokens.pop()
                        if t != '(':
                            output.append(t)
                        else: # t == '('
                            break

                else:
                    output.append(tokens.pop())
                    tokens.append(ele)

            elif OP_LEVEL[ele] < OP_LEVEL[last_op]: # [+ *] <- '-'
                while (tokens):
                    t = tokens.pop()
                    if t == '(':
                        tokens.append(t)
                        tokens.append(ele)
                        break
                    if OP_LEVEL[t] >= OP_LEVEL[ele]:
                        output.append(t)
                    else:
                        tokens.append(t)
                        tokens.append(ele)
                        break
                else:  # if [] is empty
                    tokens.append(ele)

        else: # not token ,just push into output
            output.append(int(ele))

    else:
        # print 'rest tokens', tokens
        while (tokens):
            tk = tokens.pop()
            output.append(tk)

    return output

def calc(polish_list):
    # input polish_list must be validated.
    calc_list = []

    while (polish_list):  # util list drianed
        token = polish_list.pop(0)
        if token in OPS:
            v1 = calc_list.pop()
            v2 = calc_list.pop()
            calculated_value = op_helper(v1, v2, token)
            calc_list.append(calculated_value)
        else:
            calc_list.append(token)

    return calculated_value


if __name__ == "__main__":
    for t in tests:
        rpl = transform_to_reverse_polish(t)
        # print 'rpl',rpl
        print calc(rpl) == eval(t)