20. 有效的括号
【注意】
1.括号匹配是使用栈解决的经典问题。
2.这个命令最后进入a目录，系统是如何知道进入了a目录呢 ，这就是栈的应用（其实可以出一道相应的面试题了）。
3.有三种不匹配的情况，第一种情况，字符串里左方向的括号多余了 ；第二种情况，括号没有多余，但是 括号的类型没有匹配上；第三种情况，字符串里右方向的括号多余了。
【代码】
1.剪枝操作：字符串如果是奇数，直接就是不匹配。
1 class Solution(object): 2 def isValid(self, s): 3 """ 4 :type s: str 5 :rtype: bool 6 """ 7 #方法1，仅使用栈 8 stack = [] 9 10 for item in s: 11 if item == '(': 12 stack.append(')') 13 elif item == '{': 14 stack.append('}') 15 elif item == '[': 16 stack.append(']') 17 elif not stack or stack[-1] != item: #栈为空的话，或和右括号不匹配的时候，对应2，3情况 18 return False 19 else: 20 stack.pop() 21 22 return True if not stack else False #s遍历完之后，如果栈不为空，对应第1种情况 23 24 #方法2.使用字典 25 stack = [] 26 mapping = { 27 '(':')', 28 '[':']', 29 '{':'}' 30 } 31 32 for item in s: 33 if item in mapping.keys(): 34 stack.append(mapping[item]) 35 elif not stack or stack[-1] != item: 36 return False 37 else: 38 stack.pop() 39 40 return True if not stack else False
1047. 删除字符串中的所有相邻重复项
【注意】
1.栈帮助我们记录了 遍历数组当前元素时候，前一个元素是什么。
2.字符串模拟栈。
【代码】
1 class Solution(object): 2 def removeDuplicates(self, s): 3 """ 4 :type s: str 5 :rtype: str 6 """ 7 #方法1.使用栈 8 res = list() 9 10 for item in s: 11 if res and res[-1] == item: 12 res.pop() 13 else: 14 res.append(item) 15 16 return ''.join(res) #字符串拼接 17 18 #方法2.使用双指针模拟栈 19 res = list(s) #字符串转成列表 20 slow = fast = 0 #双指针 21 n = len(res) 22 23 while fast < n: 24 #如果一样直接换，不一样会把后面的填在slow的位置 25 res[slow] = res[fast] 26 27 #如果发现和前一个一样，就退一格指针 28 if slow > 0 and res[slow] == res[slow-1]: 29 slow -= 1 30 else: 31 slow += 1 32 fast += 1 33 34 return ''.join(res[0:slow])
150. 逆波兰表达式求值
【注意】
1.逆波兰表达式就是一种后缀表达式。计算机进行顺序处理，不用关心优先级。
2.遇见数字就存放在栈里，遇见运算符就从栈里取数字，做一个计算，再把计算完的数字存放在栈里。
【代码】
1 class Solution(object): 2 op_map = {'+':add, '-':sub, '*':mul, '/':lambda x,y: int(x/y)} 3 def evalRPN(self, tokens): 4 """ 5 :type tokens: List[str] 6 :rtype: int 7 """ 8 # stack = [] 9 # for token in tokens: 10 # if token not in {'+','-','*','/'}: 11 # stack.append(int(token)) 12 # else: 13 # op1 = stack.pop() 14 # op2 = stack.pop() 15 # stack.append(self.op_map[token](op1,op2)) 16 17 # return stack.pop() 18 19 #方法2.使用eval 对字符串进行计算 20 stack = [] 21 for item in tokens: 22 if item not in {'+','-','*','/'}: 23 stack.append(item) 24 else: 25 first_num, second_num = stack.pop(), stack.pop() 26 # 第一个出来的在运算符后面 27 stack.append(int(eval(f"{second_num}{item}{first_num}"))) #力扣上提示该语句语法错误，为什么？ 28 29 # 如果一开始只有一个数，那么会是字符串形式的 30 return int(stack.pop())