匹配括號

接下來，我們使用棧解決實際的計算機科學(xué)問題。?

比如我們都寫過這樣所示的算術(shù)表達式， ( 5 + 6 ) ∗ ( 7 + 8 ) / ( 4 + 3 ) (5 + 6) * (7 + 8) / (4 + 3) (5+6)∗(7+8)/(4+3)，其中的括號用來改變計算順序，或提升運算優(yōu)先級。?

匹配括號是指每一個左括號都有與之對應(yīng)的一個右括號，并且括號對有正確的嵌套關(guān)系。

• 正確的嵌套關(guān)系： ( ( ) ( ) ( ) ( ) ) (()()()()) (()()()())、 ( ( ( ( ) ) ) ) (((()))) (((())))、 ( ( ) ( ( ( ) ) ( ) ) ) (()((())())) (()((())()))
• 錯誤的嵌套關(guān)系： ( ( ( ( ( ( ( ) ) ((((((()) ((((((())、 ( ) ) ) ())) ()))

?我們的挑戰(zhàn)就是編寫一個算法，它從左到右讀取一個括號串(不包括其他數(shù)字與運算符)，然后判斷其中的括號是否匹配。?

為了解決這個問題， 需要注意到一個重要現(xiàn)象。當從左到右處理括號時，最右邊的無匹配左括號必須與接下來遇到的第一個右括號相匹配。并且，在第一個位置的左括號可能要等到處理至最后一個位置的右括號時才能完成匹配。而且右括號的出現(xiàn)順序，與其相匹配的左括號的出現(xiàn)順序相反。這一規(guī)律暗示著能夠運用棧來解決括號匹配問題。

一旦認識到用棧來保存括號，算法編寫起來就會十分容易。?

由一個空棧開始，從左往右依次處理括號。如果遇到左括號，便通過棧的push操作將其加入棧中，以此表示稍后需要有一個與之匹配的右括號。

反之，如果遇到右括號，就調(diào)用棧的pop操作。只要棧中的所有左括號都能遇到與之匹配的右括號，那么整個括號串就是匹配的；如果棧中有任何一個左括號找不到與之匹配的右括號，則括號串就是不匹配的。在處理完匹配的括號串之后，棧應(yīng)該是空的。?

用簡單的話說就是：掃描括號串，左括號入棧，遇見右括號，從棧頂取出來一個左括號配對兒，互相抵消，直到最后。如果括號匹配，那么棧最后就該是空的，并且括號串剛好掃描完畢。

代碼實現(xiàn)如下：

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()  # 構(gòu)造棧
    balanced = True  # 匹配標志 默認為True 表示匹配
    index = 0  # 索引 用來取字符
    # 當 索引小于字符串的長度 并且 匹配標志為True 時
    while index < len(symbolString) and balanced:
        # 取字符串當前位的字符
        symbol = symbolString[index]
        # 如果當前字符為 左括號 則入棧
        if symbol == '(':
            s.push(symbol)
        # 如果當前字符 不是左括號(那當前就是右括號)
        else:
            # 并且棧是空的
            if s.isEmpty():
                # 匹配標志設(shè)置為 False 表示匹配失敗(孤零零的右括號)
                balanced = False
            # 棧不是空的 抵消棧頂?shù)淖罄ㄌ?
            else:
                s.pop()
        # 索引向后移動一位
        index = index + 1
    # 循環(huán)結(jié)束 如果匹配成功 并且 ?？樟?
    if balanced and s.isEmpty():
        return True
    else:
        return False

注意，balanced 的初始值是True，這是因為一開始沒有任何理由假設(shè)其為False 。如果當前的符號是左括號，它就會被壓入棧中（第27行）。注意第36行，僅通過pop()將一個元素從棧頂移除。由于移除的元素一定是之前遇到的左括號，因此并沒有用到pop()的返回值。在第42~45行， 只要所有括號匹配并且棧為空，函數(shù)就會返回True ，否則返回False。?

匹配符號

符號匹配是許多編程語言中的常見問題，括號匹配問題只是它的一個特例。我們已經(jīng)會了匹配括號的方法，那么現(xiàn)在我們來試試匹配符號。?

匹配符號是指正確地匹配和嵌套左右對應(yīng)的符號。?

例如，在Python中，方括號“[”和“]”用于列表；花括號“{”和“}”用于字典；括號“(”和“)”用于元組和算術(shù)表達式。只要保證左右符號匹配，就可以混用這些符號。以下符號串是匹配的，其中不僅每一個左符號都有一個右符號與之對應(yīng)，而且兩個符號的類型也是一致的。

• { { ( [ ] [ ] ) } ( ) }
• [ [ { { ( ( ) ) } } ] ]
• [ ] [ ] [ ] ( ) { }

?以下符號則是不匹配的：

• ( [ ) ]
• ( ( ( ) ] ) )
• [ { ( ) ]

?要處理新類型的符號，我們擴展上面的括號匹配檢測代碼。?

即每一個左符號都將被壓入棧中，以待之后出現(xiàn)對應(yīng)的右符號。?

唯一的區(qū)別在于，當出現(xiàn)右符號時，必須先檢測其類型是否與棧頂?shù)淖蠓栴愋?/strong>相匹配。如果兩個符號不匹配，那么整個符號串也就不匹配。同樣，如果整個符號串處理完成并且棧是空的，那么就說明所有符號正確匹配。

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()  # 構(gòu)造棧
    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():
                # 匹配標志設(shè)置為 False 表示匹配失敗(孤零零的右括號)
                balanced = False
            # 棧不是空的 拿出棧頂?shù)淖罄ㄌ栠M行類型匹配
            else:
                top = s.pop()
                # 類型匹配失敗
                if not matches(top, symbol):
                    balanced = False
        # 索引向后移動一位
        index = index + 1
    # 循環(huán)結(jié)束 如果匹配成功 并且 ?？樟?
    if balanced and s.isEmpty():
        return True
    else:
        return False

def matches(left, right):
    lefts = "([{"
    rights = ")]}"
    # 調(diào)用字符串的index方法，index() 方法查找指定值的首次出現(xiàn)，并返回索引。
    # 左右索引對應(yīng)，表明符號匹配
    return lefts.index(left) == rights.index(right)