题目

给你一个字符串表达式 s，请你实现一个根本计算器来计算并返回它的值。

输出：s = "1 + 1"
输入：2

输出：s = "2-1 + 2"
输入：3

输出：s = "(1+(4+5+2)-3)+(6+8)"
输入：23

s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 示意一个无效的表达式
'+' 不能用作一元运算(例如，"+1" 和 "+(2 + 3)" 有效)
'-' 能够用作一元运算(即 "-1" 和 "-(2 + 3)" 是无效的)
输出中不存在两个间断的操作符
每个数字和运行的计算将适宜于一个有符号的 32 位 整数

思路

计算器类的题目，224、227、772，只须要一个思路：逆波兰表达式 + 栈。
a+b，逆波兰表达式：a,b,+

例如：s = ‘2+(35/4+7(2+3))/4′

定义两个栈：
stack 栈 用来寄存数字以外的符号：运算符、括号
res 栈 用来寄存数字，以及 pop 进去的运算符，造成逆波兰表达式

给出一个加减乘除全都有的思路：
思路规定：
数字，放入 res
符号，放入 stack
当以后符号的优先级，<=stack 栈顶的符号优先级时，须要将 stack 栈顶的符号 pop 进来，放入 res 中，再将以后符号放入 stack 中
当遇到）时，将 stack 中最初一个（之后的所有运算符都 pop 进来，放入 res 中

构建逆波兰表达式的过程：

2+(3*5/4+7*(2+3))/4

以后字符 2，压入 res
stack: []
res: ['2']

以后字符 +，压入 stack
stack: ['+']
res: ['2']

以后字符是 (，压入 stack
stack: ['+', '(']
res: ['2']

以后字符 3，压入 res
stack: ['+', '(']
res: ['2', '3']

以后字符 *，压入 stack
stack: ['+', '(', '*']
res: ['2', '3']

以后字符 5，压入 res
stack: ['+', '(', '*']
res: ['2', '3', '5']

以后字符 /，优先级 <=stack 栈顶的 *, 将 stack 栈顶的 * pop 到 res 中，再将以后的 / 压入 stack
stack: ['+', '(', '/']
res: ['2', '3', '5', '*']

以后字符 4，压入 res
stack: ['+', '(', '/']
res: ['2', '3', '5', '*', '4']

以后字符 +，优先级 <=stack 栈顶的 /, 将 stack 栈顶的 / pop 到 res 中，再将以后的 + 压入 stack
stack: ['+', '(', '+']
res: ['2', '3', '5', '*', '4', '/']

以后字符 7，压入 res
stack: ['+', '(', '+']
res: ['2', '3', '5', '*', '4', '/', '7']

以后字符 *，压入 stack
stack: ['+', '(', '+', '*']
res: ['2', '3', '5', '*', '4', '/', '7']

以后字符是 (，压入 stack
stack: ['+', '(', '+', '*', '(']
res: ['2', '3', '5', '*', '4', '/', '7']

以后字符 2，压入 res
stack: ['+', '(', '+', '*', '(']
res: ['2', '3', '5', '*', '4', '/', '7', '2']

以后字符 +，压入 stack
stack: ['+', '(', '+', '*', '(', '+']
res: ['2', '3', '5', '*', '4', '/', '7', '2']

以后字符 3，压入 res
stack: ['+', '(', '+', '*', '(', '+']
res: ['2', '3', '5', '*', '4', '/', '7', '2', '3']

以后字符 )，将 stack 中最初一个 ( 之后的运算符都 pop 到 res 中
stack: ['+', '(', '+', '*']
res: ['2', '3', '5', '*', '4', '/', '7', '2', '3', '+']

以后字符 )，将 stack 中最初一个 ( 之后的运算符都 pop 到 res 中
stack: ['+']
res: ['2', '3', '5', '*', '4', '/', '7', '2', '3', '+', '*', '+']

以后字符 /，压入 stack
stack: ['+', '/']
res: ['2', '3', '5', '*', '4', '/', '7', '2', '3', '+', '*', '+']

以后字符 4，压入 res
stack: ['+', '/']
res: ['2', '3', '5', '*', '4', '/', '7', '2', '3', '+', '*', '+', '4']

stack 中残余的操作符，后进先出的 pop 到 res 中
stack: []
res: ['2', '3', '5', '*', '4', '/', '7', '2', '3', '+', '*', '+', '4', '/', '+']

逆波兰表达式计算过程:

字符: 2
入栈: [2]

字符: 3
入栈: [2, 3]

字符: 5
入栈: [2, 3, 5]

字符: *
取出栈顶后两位进行相应的运算，后果入栈: [2, 15]

字符: 4
入栈: [2, 15, 4]

字符: /
取出栈顶后两位进行相应的运算，后果入栈: [2, 3]

字符: 7
入栈: [2, 3, 7]

字符: 2
入栈: [2, 3, 7, 2]

字符: 3
入栈: [2, 3, 7, 2, 3]

字符: +
取出栈顶后两位进行相应的运算，后果入栈: [2, 3, 7, 5]

字符: *
取出栈顶后两位进行相应的运算，后果入栈: [2, 3, 35]

字符: +
取出栈顶后两位进行相应的运算，后果入栈: [2, 38]

字符: 4
入栈: [2, 38, 4]

字符: /
取出栈顶后两位进行相应的运算，后果入栈: [2, 9]

字符: +
取出栈顶后两位进行相应的运算，后果入栈: [11]

python 代码：

def calculate(s: str) -> int:
    if s.strip().isdigit():
            return int(s)
    n = len(s)
    stack = [] # 用来存运算符和括号的栈
    res = [] # 用来存数字的栈
    dic = { # 操作符优先级字典
        '+':1,
        '-':1,
        '*':2,
        '/':2,
        '%':2,
        '^':3
    }
    for i in range(n):
        # 打印日志
        underline = '\033[4m'
        end = '\033[0m'
        print(s[0:i]+underline + s[i] + end+s[i+1:])
        if s[i]==' ':
            continue
        # 1. 遇到数字，间接压入 res 栈
        if s[i].isdigit():
            #‘11’这种，前一位也是数字的，须要进行解决
            if i!=0 and s[i-1].isdigit():
                print('以后字符 %s，前一个字符也是数字 %s，非凡解决'%(s[i],s[i-1]))
                res.append(str(int(res.pop())*10+int(s[i])))
            else:
                print('以后字符 %s，压入 res'%(s[i]))
                res.append(s[i])
        else:
            # 2. 遇到右括号，将 stack 栈顶到最近的左括号之间的运算符，后进先出的 pop 到 res 中
            if s[i]==')':
                print('以后字符 %s，将 stack 中最初一个 ( 之后的运算符都 pop 到 res 中'%(s[i]))
                while True:
                    if stack[-1]=='(':
                        stack.pop()
                        break
                    else:
                        res.append(stack.pop())
            # 3. 遇到左括号，间接压入 stack
            elif s[i]=='(':
                print('以后字符是 (，压入 stack')
                stack.append('(')
            # 4. '-2+1' 和 '1-(-2+1)' 这两边界状况，将 - 2 当作 0 - 2 解决，在 res 中也压入 0
            elif s[i]=='-' and (i==0 or s[i-1]=='(') :
                print('以后字符是 -，后面是(或着没有字符，当作 0 - 解决，res 中压入 0，stack 压入 -')
                res.append('0')
                stack.append('-')
            else:
                print('以后字符 %s'%s[i],end='，')
                # 5. 遇到运算符，压入 stack 栈
                # 如果以后运算符优先级 <= stack 栈顶运算符优先级，# 则将 stack 栈定的运算符 pop 到 res 栈中，再压入以后运算符到 stack
                if len(stack) and stack[-1] in dic and dic[s[i]]<=dic[stack[-1]]:
                    print('优先级 <=stack 栈顶的 %s, 将 stack 栈顶的 %s pop 到 res 中，再将以后的 %s 压入 stack'%(stack[-1],stack[-1],s[i]))
                    res.append(stack.pop())
                    stack.append(s[i])
                else:
                    print('压入 stack')
                    # 否则间接压入 stack 栈中
                    stack.append(s[i])
        print('stack:',stack)
        print('res:',res)
        print('\n')
                    
    # 最初将 stack 中残余的操作符，后进先出的 pop 到 res 中
    for _ in range(len(stack)):
        res.append(stack.pop())
#     print('stack 中残余的操作符，后进先出的 pop 到 res 中')
#     print('stack:',stack)
#     print('res:',res)
    
    # res 就是最终的逆波兰表达式，开始计算 res 的值
    # 再新建一个空栈_res，遍历逆波兰表达式，将数字压入到_res 中
    # 当遍历到运算符时，_res 栈中最初两个数字就是参加该运算的数字
    # 留神：要留神数字的程序，a,b,/ => a/b, a,b,^= a**b
    _res = []
    for ch in res:
#         print('字符:',ch)
        if ch.isdigit():
            _res.append(int(ch))
#             print('入栈:',_res)
        else:
            b = _res.pop()
            a = _res.pop()
            if ch=='+':
                _res.append(a+b)
            elif ch=='-':
                _res.append(a-b)
            elif ch=='*':
                _res.append(a*b)
            elif ch=='/':
                _res.append(a//b)
            elif ch=='%':
                _res.append(a%b)
            elif ch=='^':
                _res.append(a**b)
#             print('取出栈顶后两位进行相应的运算，后果入栈:',_res)
#         print('\n')

    return _res

无 print 清新版：

def calculate(s: str) -> int:
    if s.strip().isdigit():
            return int(s)
    n = len(s)
    stack = []
    res = []
    dic = {
        '+':1,
        '-':1,
        '*':2,
        '/':2,
        '%':2,
        '^':3
    }
    for i in range(n):
        if s[i]==' ':
            continue
        if s[i].isdigit():
            if i!=0 and s[i-1].isdigit():
                res.append(str(int(res.pop())*10+int(s[i])))
            else:
                res.append(s[i])
        else:
            if s[i]==')':
                while True:
                    if stack[-1]=='(':
                        stack.pop()
                        break
                    else:
                        res.append(stack.pop())
            elif s[i]=='(':
                stack.append('(')
            elif s[i]=='-' and (i==0 or s[i-1]=='(') :
                res.append('0')
                stack.append('-')
            else:
                if len(stack) and stack[-1] in dic and dic[s[i]]<=dic[stack[-1]]:
                    res.append(stack.pop())
                    stack.append(s[i])
                else:
                    stack.append(s[i])

    for _ in range(len(stack)):
        res.append(stack.pop())

    _res = []
    for ch in res:
        if ch.isdigit():
            _res.append(int(ch))
        else:
            b = _res.pop()
            a = _res.pop()
            if ch=='+':
                _res.append(a+b)
            elif ch=='-':
                _res.append(a-b)
            elif ch=='*':
                _res.append(a*b)
            elif ch=='/':
                _res.append(a//b)
            elif ch=='%':
                _res.append(a%b)
            elif ch=='^':
                _res.append(a**b)

    return _res

边界状况总结：

• ‘123456’, ‘ 123456’，s 间接就是一串数字字符串，代码结尾 s.strip().isdigit()判断一下间接返回即可。
• ‘-2+1’，1-(-2)’，在字符串结尾或者(后，接一个符号，按 0 - 2 解决
• ‘1+111’，多位数的判断，res.append(str(int(res.pop())*10+int(s[i])))