LeetCode20 有效的括号
题目链接/文章讲解/视频讲解：https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html
⭐括号匹配
先讨论有3种不匹配的情况：
- 第一种情况，字符串里左方向的括号多余了，所以不匹配。
- 第二种情况，括号没有多余，但是括号的类型没有匹配上。
- 第三种情况，字符串里右方向的括号多余了，所以不匹配。
动画如下：
第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false
第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false
第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false
那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。
但还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
for i in s:
# 遇到左括号，先把对应右括号压栈
if i == '(':
stack.append(')')
elif i == '[':
stack.append(']')
elif i == '{':
stack.append('}')
elif not stack or stack[-1] != i: # 情况3和情况2
return False
else:
stack.pop() # 匹配
if stack: # 情况1
return False
return True
LeetCode1047 删除字符串中的所有相邻重复项
✌思路：每次要压入栈中的元素和栈顶比较，如果相同说明重复，pop栈顶，否则push
class Solution(object):
def removeDuplicates(self, s):
"""
:type s: str
:rtype: str
"""
stack = []
for i in s:
if stack and stack[-1] == i: # 重复
stack.pop()
else:
stack.append(i)
return "".join(stack)
LeetCode150 逆波兰表达式求值
题目链接/文章讲解/视频讲解：https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html
逆波兰表达式相当于是二叉树中的后序遍历：逆波兰表达式是用后序遍历的方式把二叉树序列化
class Solution(object):
def evalRPN(self, tokens):
"""
:type tokens: List[str]
:rtype: int
"""
stack = []
for i in tokens:
# 如果加入的数字，直接push
if i not in {"+", "-", "*", "/"}:
stack.append(int(i))
# 如果加入的是运算符，pop栈顶两项数字做运算，把结果push
else:
num1, num2 = stack.pop(), stack.pop()
stack.append(self.evaluate(num2, num1, i)) # 第一个出来的在运算符后面
return int(stack.pop())
def evaluate(self, num1, num2, op):
if op == "+":
return num1 + num2
elif op == "-":
return num1 - num2
elif op == "*":
return num1 * num2
elif op == "/":
return int(num1 / float(num2))
