栈
极客时间上王争老师说：
关于“栈”，我有一个非常贴切的例子，就是一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。
后进者先出，先进者后出，这就是典型的“栈”结构。
括号匹配问题
课程中老师提到了栈在括号匹配中的应用
栈-括号匹配
Python 代码实现
其实栈，不用特别去定义一个类，就用 Python 的 list 就可以了。
入栈：就用 list 的 append() 方法，添加到 list 尾部
出栈：就用 list 的 pop() 方法，从 list 尾部取出一个
这样操作跟栈的后进先出，是同理的。
版本1
遇到左括号入栈，否则就从栈里面拿出来进行匹配
def isValid(s):
stack = []
brackets= {'{':'}','(':')','[':']'} # 左括号当key， 右括号当value
for ch in s:
if ch in brackets: # 如果ch是左括号，则入栈
stack.append(ch)
elif not stack or ch != brackets[stack.pop()]: # 如果ch是‘右括号’，那么用栈顶元素当值去取value，也就能找到对应的右括号；如果没有或匹配不上，失败
return False
return not stack # 最后，判断stack是否为空，为空也是匹配成功
print(isValid('{()[]}'))
版本2
遇到右括号入栈，否则就从栈里面拿出来进行匹配
版本1和版本2的区别在于，括号组成的 map 的定义方式，和取元素的方式有一点点区别，具体看代码
def isValid(s):
stack = []
brackets= {
'}':'{',
')':'(',
']':'['
} # 右括号当key， 左括号当value
for ch in s:
if ch not in brackets: # 如果ch不是右括号，则压栈
stack.append(ch)
elif not stack or brackets[ch]!=stack.pop(): # 如果ch是‘右括号’，那么栈顶元素一定可以找到与之对应的‘左括号’；如果没有，匹配失败
return False
return not stack # 最后，判断stack是否为空，写法比较简洁
print(isValid('{[]()}'))
谢谢你的阅读~
题图：pixabay.com
参考资料：
