學點演算法之棧的學習與應用

原文：學點演算法之棧的學習與應用

在學習棧前，腦海中對這個詞只有一個印象：客棧

棧是什麼

棧（有時稱為「後進先出棧」）是一個項的有序集合，其中添加移除新項總發生在同一端。

這段話初學者是懵逼的，別急，往下看。

對棧的一般操作：

• Stack() 創建一個空的新棧。 它不需要參數，並返回一個空棧。
• push(item)將一個新項添加到棧的頂部。它需要 item 做參數並不返回任何內容。
• pop() 從棧中刪除頂部項。它不需要參數並返回 item 。棧被修改。
• peek() 從棧返回頂部項，但不會刪除它。不需要參數。 不修改棧。
• isEmpty() 測試棧是否為空。不需要參數，並返回布爾值。
• size() 返回棧中的 item 數量。不需要參數，並返回一個整數。

例如，s 是已經創建的空棧，下圖展示了棧操作序列的結果。棧中，頂部項列在最右邊。

自己在心裡過一遍就很好理解了

Python實現棧

其實看到上面那張圖，就想起了Python中 list 的一些用法，append、pop等，下面是使用 Python 來實現棧，也非常簡單：

class Stack: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def peek(self): return self.items[len(self.items)-1] def size(self): return len(self.items)

pythonds/basic/stack.py

棧的應用：簡單括弧匹配（一）

有一些正確匹配的括弧字元串：

(()()()())(((())))(()((())()))

對比那些不匹配的括弧：

((((((())()))(()()(()

具有挑戰的是如何編寫一個演算法，能夠從左到右讀取一串符號，並決定符號是否平衡。

為了解決這個問題，我們需要做一個重要的觀察。從左到右處理符號時，最近開始符號必須與下一個關閉符號相匹配。此外，處理的第一個開始符號必須等待直到其匹配最後一個符號。結束符號以相反的順序匹配開始符號。他們從內到外匹配。這是一個可以用棧解決問題的線索。

from pythonds.basic.stack import Stackdef parChecker(symbolString): s = Stack() balanced = True index = 0 while index < len(symbolString) and balanced: symbol = symbolString[index] if symbol == "(": s.push(symbol) else: if s.isEmpty(): balanced = False else: s.pop() index = index + 1 if balanced and s.isEmpty(): return True else: return Falseprint(parChecker(((()))))print(parChecker((()))

output

TrueFalse

一旦你認為棧是保存括弧的恰當的數據結構，演算法是很直接的。

從空棧開始，從左到右處理括弧字元串。如果一個符號是一個開始符號，將其作為一個信號，對應的結束符號稍後會出現。另一方面，如果符號是結束符號，彈出棧，只要彈出棧的開始符號可以匹配每個結束符號，則括弧保持匹配狀態。如果任何時候棧上沒有出現符合開始符號的結束符號，則字元串不匹配。最後，當所有符號都被處理後，棧應該是空的。

如果有和我一樣不能很好理解的，使用pycharm的debug模式，可以一步步來，看看程序就近在做什麼。

括弧配對問題（二）

來看看第二種匹配問題。Python程序里存在很多括弧：如圓括弧、方括弧和花括弧，每種括弧都有開括弧和閉括弧。

from pythonds.basic.stack import Stackpares = "()[]{}"def pare_theses(text): i, text_len = 0, len(text) while True: while i < text_len and text[i] not in pares: i += 1 if i >= text_len: return yield text[i], i i += 1def check_pares(text): open_pares = "([{" opposite = {): (, ]: [, }: {} # 表示配對關係的字典 s = Stack() for pr, i in pare_theses(text): if pr in open_pares: # 開括弧，壓進棧並繼續 s.push(pr) elif s.pop() != opposite[pr]: # 不匹配就是失敗，退出 print(Unmatching is found at, i, for, pr) return False # else 是一次括弧配對成功，什麼也不做，繼續 print("All paretheses are correctly matched.") return Truecheck_pares(([]{}])check_pares(([]{}))

output

Unmatching is found at 5 for ]All paretheses are correctly matched.

生成器（回憶一下）：

參考

1. http://interactivepython.org/runestone/static/pythonds/BasicDS/TheStackAbstractDataType.html
2. http://www.math.pku.edu.cn/teachers/qiuzy/ds_python/courseware/index.htm

如果對你有幫助，可以來關注我的公眾號：zhangslob