题目
给你一个字符串表达式 s ，请你实现一个根本计算器来计算并返回它的值。
输出：s = "1 + 1"输入：2输出：s = " 2-1 + 2 "输入：3输出：s = "(1+(4+5+2)-3)+(6+8)"输入：23s 由数字、'+'、'-'、'('、')'、和 ' ' 组成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，压入resstack: []res: ['2']以后字符 +，压入stackstack: ['+']res: ['2']以后字符是 (，压入stackstack: ['+', '(']res: ['2']以后字符 3，压入resstack: ['+', '(']res: ['2', '3']以后字符 *，压入stackstack: ['+', '(', '*']res: ['2', '3']以后字符 5，压入resstack: ['+', '(', '*']res: ['2', '3', '5']以后字符 /，优先级<=stack栈顶的*, 将stack栈顶的* pop到res中，再将以后的/压入stackstack: ['+', '(', '/']res: ['2', '3', '5', '*']以后字符 4，压入resstack: ['+', '(', '/']res: ['2', '3', '5', '*', '4']以后字符 +，优先级<=stack栈顶的/, 将stack栈顶的/ pop到res中，再将以后的+压入stackstack: ['+', '(', '+']res: ['2', '3', '5', '*', '4', '/']以后字符 7，压入resstack: ['+', '(', '+']res: ['2', '3', '5', '*', '4', '/', '7']以后字符 *，压入stackstack: ['+', '(', '+', '*']res: ['2', '3', '5', '*', '4', '/', '7']以后字符是 (，压入stackstack: ['+', '(', '+', '*', '(']res: ['2', '3', '5', '*', '4', '/', '7']以后字符 2，压入resstack: ['+', '(', '+', '*', '(']res: ['2', '3', '5', '*', '4', '/', '7', '2']以后字符 +，压入stackstack: ['+', '(', '+', '*', '(', '+']res: ['2', '3', '5', '*', '4', '/', '7', '2']以后字符 3，压入resstack: ['+', '(', '+', '*', '(', '+']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', '+', '*', '+']以后字符 /，压入stackstack: ['+', '/']res: ['2', '3', '5', '*', '4', '/', '7', '2', '3', '+', '*', '+']以后字符 4，压入resstack: ['+', '/']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])))