棧
極客時(shí)間上王爭(zhēng)老師說(shuō)：
關(guān)于“棧”头滔，我有一個(gè)非常貼切的例子，就是一摞疊在一起的盤(pán)子涎显。我們平時(shí)放盤(pán)子的時(shí)候坤检，都是從下往上一個(gè)一個(gè)放；取的時(shí)候期吓，我們也是從上往下一個(gè)一個(gè)地依次取早歇，不能從中間任意抽出。
后進(jìn)者先出讨勤，先進(jìn)者后出箭跳，這就是典型的“棧”結(jié)構(gòu)潭千。
括號(hào)匹配問(wèn)題
課程中老師提到了棧在括號(hào)匹配中的應(yīng)用
棧-括號(hào)匹配
Python 代碼實(shí)現(xiàn)
其實(shí)棧谱姓，不用特別去定義一個(gè)類，就用 Python 的 list 就可以了刨晴。
入棧：就用 list 的 append() 方法屉来，添加到 list 尾部
出棧：就用 list 的 pop() 方法，從 list 尾部取出一個(gè)
這樣操作跟棧的后進(jìn)先出狈癞，是同理的奶躯。
版本1
遇到左括號(hào)入棧，否則就從棧里面拿出來(lái)進(jìn)行匹配
def isValid(s):
stack = []
brackets= {'{':'}','(':')','[':']'} # 左括號(hào)當(dāng)key亿驾， 右括號(hào)當(dāng)value
for ch in s:
if ch in brackets: # 如果ch是左括號(hào)嘹黔，則入棧
stack.append(ch)
elif not stack or ch != brackets[stack.pop()]: # 如果ch是‘右括號(hào)’，那么用棧頂元素當(dāng)值去取value莫瞬，也就能找到對(duì)應(yīng)的右括號(hào)儡蔓；如果沒(méi)有或匹配不上，失敗
return False
return not stack # 最后疼邀，判斷stack是否為空喂江，為空也是匹配成功
print(isValid('{()[]}'))
版本2
遇到右括號(hào)入棧，否則就從棧里面拿出來(lái)進(jìn)行匹配
版本1和版本2的區(qū)別在于旁振，括號(hào)組成的 map 的定義方式获询，和取元素的方式有一點(diǎn)點(diǎn)區(qū)別，具體看代碼
def isValid(s):
stack = []
brackets= {
'}':'{',
')':'(',
']':'['
} # 右括號(hào)當(dāng)key拐袜， 左括號(hào)當(dāng)value
for ch in s:
if ch not in brackets: # 如果ch不是右括號(hào)吉嚣，則壓棧
stack.append(ch)
elif not stack or brackets[ch]!=stack.pop(): # 如果ch是‘右括號(hào)’，那么棧頂元素一定可以找到與之對(duì)應(yīng)的‘左括號(hào)’蹬铺；如果沒(méi)有尝哆，匹配失敗
return False
return not stack # 最后，判斷stack是否為空甜攀，寫(xiě)法比較簡(jiǎn)潔
print(isValid('{[]()}'))
謝謝你的閱讀~
題圖：pixabay.com
參考資料：
極客時(shí)間：https://time.geekbang.org/column/article/41222
有效括號(hào)問(wèn)題：https://www.cnblogs.com/wl413911/p/12923951.html
