op_order = {'*': 1, '/': 1, '+': 2, '-': 2}

def is_operand(input):
    return input == '+' or input == '-' or input =='*' or input == '/'

def is_non_number(input):
    return input == '(' or input == ')' or is_operand(input)

def compute(left, right, op):

    if op == '+':
        return left + right
    elif op == '-':
        return left - right
    elif op == '*':
        return left * right
    elif op == '/':
        return left / right

def convert_to_polish(expr):

    queue = []
    op_stack = []
    prev = None

    for i in range(len(expr)):
        cur = expr[i]

        if is_non_number(cur) == True:
           # empty the prev if not empty
            if prev is not None:
                queue.append(int(prev))
                prev = None

            if cur == '(':
                op_stack.append(cur)
            elif cur == ')':
                # pop all pos in the stack until '(' and add to the queue
                while len(op_stack) > 0:
                    op = op_stack.pop()
                    if op == '(':
                        break

                    queue.append(op)
            elif is_operand(cur) == True:

                # pop all Ops lower or equal to the current one.
                while len(op_stack) > 0 and op_stack[-1] != '(' and op_order[cur] >= op_order[op_stack[-1]]:
                    op = op_stack.pop()
                    queue.append(op)
                
                op_stack.append(cur)
        else: # number
            prev = prev + cur if prev is not None else cur
    
    if prev is not None:
        queue.append(int(prev))

    # empty the rest of operand
    while len(op_stack) > 0:
        queue.append(op_stack.pop())

    return queue


def calculate(input):
    queue = convert_to_polish(input)

    print(queue)

    num_stack = []
    # now start computing
    while len(queue) > 0:
        cur = queue.pop(0)
        if is_operand(cur) != True:
            num_stack.append(cur)
        else:
            right = num_stack.pop()
            left = num_stack.pop()
            result = compute(left, right, cur)
            num_stack.append(result)

    return num_stack.pop() if len(num_stack) == 1 else None


input = ['1*(4+1)' ,'2+(3+3)-4*2+12/3', '3+4/2*(3+2)', '100/2+(50-10)/2+1000']
expected= [5,4, 13, 1070]

actual = []
for i in input:
    output =calculate(i)
    actual.append(output)

print("expected = {}, actual={}".format(expected, actual))