Python數據結構與算法中的棧詳解(2)
匹配括號
接下來，我們使用棧解決實際的計算機科學問題。
比如我們都寫過這樣所示的算術表達式， ( 5 + 6 ) ∗ ( 7 + 8 ) / ( 4 + 3 ) (5 + 6) * (7 + 8) / (4 + 3) (5+6)∗(7+8)/(4+3)，其中的括號用來改變計算順序，或提升運算優先級。
匹配括號是指每一個左括號都有與之對應的一個右括號，並且括號對有正確的嵌套關系。
- 正確的嵌套關系： ( ( ) ( ) ( ) ( ) ) (()()()()) (()()()())、 ( ( ( ( ) ) ) ) (((()))) (((())))、 ( ( ) ( ( ( ) ) ( ) ) ) (()((())())) (()((())()))
- 錯誤的嵌套關系： ( ( ( ( ( ( ( ) ) ((((((()) ((((((())、 ( ) ) ) ())) ()))
我們的挑戰就是編寫一個算法，它從左到右讀取一個括號串(不包括其他數字與運算符)，然後判斷其中的括號是否匹配。
為瞭解決這個問題， 需要註意到一個重要現象。當從左到右處理括號時，最右邊的無匹配左括號必須與接下來遇到的第一個右括號相匹配。並且，在第一個位置的左括號可能要等到處理至最後一個位置的右括號時才能完成匹配。而且右括號的出現順序，與其相匹配的左括號的出現順序相反。這一規律暗示著能夠運用棧來解決括號匹配問題。
一旦認識到用棧來保存括號，算法編寫起來就會十分容易。
由一個空棧開始，從左往右依次處理括號。如果遇到左括號，便通過棧的push操作將其加入棧中，以此表示稍後需要有一個與之匹配的右括號。
反之，如果遇到右括號，就調用棧的pop操作。隻要棧中的所有左括號都能遇到與之匹配的右括號，那麼整個括號串就是匹配的；如果棧中有任何一個左括號找不到與之匹配的右括號，則括號串就是不匹配的。在處理完匹配的括號串之後，棧應該是空的。
用簡單的話說就是：掃描括號串，左括號入棧，遇見右括號，從棧頂取出來一個左括號配對兒，互相抵消，直到最後。如果括號匹配，那麼棧最後就該是空的，並且括號串剛好掃描完畢。
代碼實現如下：
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 parChecker(symbolString):
s = Stack() # 構造棧
balanced = True # 匹配標志 默認為True 表示匹配
index = 0 # 索引 用來取字符
# 當 索引小於字符串的長度 並且 匹配標志為True 時
while index < len(symbolString) and balanced:
# 取字符串當前位的字符
symbol = symbolString[index]
# 如果當前字符為 左括號 則入棧
if symbol == '(':
s.push(symbol)
# 如果當前字符 不是左括號(那當前就是右括號)
else:
# 並且棧是空的
if s.isEmpty():
# 匹配標志設置為 False 表示匹配失敗(孤零零的右括號)
balanced = False
# 棧不是空的 抵消棧頂的左括號
else:
s.pop()
# 索引向後移動一位
index = index + 1
# 循環結束 如果匹配成功 並且 棧空瞭
if balanced and s.isEmpty():
return True
else:
return False
註意，balanced 的初始值是True，這是因為一開始沒有任何理由假設其為False 。如果當前的符號是左括號，它就會被壓入棧中（第27行）。註意第36行，僅通過pop()將一個元素從棧頂移除。由於移除的元素一定是之前遇到的左括號，因此並沒有用到pop()的返回值。在第42~45行， 隻要所有括號匹配並且棧為空，函數就會返回True ，否則返回False。
匹配符號
符號匹配是許多編程語言中的常見問題，括號匹配問題隻是它的一個特例。我們已經會瞭匹配括號的方法，那麼現在我們來試試匹配符號。
匹配符號是指正確地匹配和嵌套左右對應的符號。
例如，在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 parChecker(symbolString):
s = Stack() # 構造棧
balanced = True # 匹配標志 默認為True 表示匹配
index = 0 # 索引 用來取字符
# 當 索引小於字符串的長度 並且 匹配標志為True 時
while index < len(symbolString) and balanced:
# 取字符串當前位的字符
symbol = symbolString[index]
# 如果當前字符屬於 左括號集 則入棧
if symbol in '([{':
s.push(symbol)
# 如果當前字符 不是左括號(那當前就是右括號)
else:
# 並且棧是空的
if s.isEmpty():
# 匹配標志設置為 False 表示匹配失敗(孤零零的右括號)
balanced = False
# 棧不是空的 拿出棧頂的左括號進行類型匹配
else:
top = s.pop()
# 類型匹配失敗
if not matches(top, symbol):
balanced = False
# 索引向後移動一位
index = index + 1
# 循環結束 如果匹配成功 並且 棧空瞭
if balanced and s.isEmpty():
return True
else:
return False
def matches(left, right):
lefts = "([{"
rights = ")]}"
# 調用字符串的index方法，index() 方法查找指定值的首次出現，並返回索引。
# 左右索引對應，表明符號匹配
return lefts.index(left) == rights.index(right)
測試結果如下圖所示：
以上兩個例子說明，在處理編程語言的語法結構時，棧是十分重要的數據結構。幾乎所有記法都有某種需要正確匹配和嵌套的符號。除此之外，棧在計算機科學中還有其他一些重要的應用場景，讓我們繼續探索。
總結
本篇文章就到這裡瞭，希望能夠給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容!