腾讯面试题：中缀表达式求值（两个栈）

• 题目描述

实现一个识别包含加法和乘法算式的程序，输出算式的计算结果，如：
输入 1+1+2*2，输出6
输入 (1+1)*2+1，输出5

• 求解：用两个栈

两个栈，一个用于保存操作符，一个用于保存数字。（也可以先用一个栈将中缀表达式转化成后缀表达式，再用一个栈计算后缀表达式的值）

'''
用两个栈计算中缀表达式的值
'''
def cal(operator, op1, op2):
    if operator == '+':
        return op1 + op2
    elif operator == '-':
        return op1 - op2
    elif operator == '*':
        return op1 * op2
    elif operator == '/':
        return op1 / op2

def exprCal(alist):
    pre = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}
    number_stack = []
    operate_stack = []
    for token in alist:
        if token.isdecimal() or token[1:].isdecimal():
            number_stack.append(int(token))
        elif token == '(':
            operate_stack.append(token)
        elif token == ')':
            while operate_stack[-1] != '(':
                op1 = number_stack.pop()
                op2 = number_stack.pop()
                res = cal(operate_stack.pop(), op2, op1)
                number_stack.append(res)
            operate_stack.pop()
        elif token in '*/+-':
            while operate_stack and pre[token] <= pre[operate_stack[-1]]:
                op1 = number_stack.pop()
                op2 = number_stack.pop()
                res = cal(operate_stack.pop(), op2, op1)
                number_stack.append(res)
            operate_stack.append(token)
    while operate_stack:
        op1 = number_stack.pop()
        op2 = number_stack.pop()
        number_stack.append(cal(operate_stack.pop(), op2, op1))
    return number_stack[0]
if __name__ == "__main__":
    s = '1+2*3/(4+5)'
    alist = list(s)
    print(exprCal(alist))

参考链接：https://www.yuque.com/docs/share/3bd692c8-4727-4f30-9f43-14c00f0c1894