每日leetcode——224.基本计算器数据结构与算法

题目给你一个字符串表达式 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，压入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

【每日leetcode——224.基本计算器】边界情况总结：