匹配括號

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

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

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

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

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

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

一旦認(rèn)識到用棧來保存括號，算法編寫起來就會(huì)十分容易。?

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

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

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

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

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

匹配符號

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

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

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

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

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

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

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

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

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

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  # 匹配標(biāo)志 默認(rèn)為True 表示匹配
    index = 0  # 索引 用來取字符
    # 當(dāng) 索引小于字符串的長度 并且 匹配標(biāo)志為True 時(shí)
    while index < len(symbolString) and balanced:
        # 取字符串當(dāng)前位的字符
        symbol = symbolString[index]
        # 如果當(dāng)前字符屬于 左括號集 則入棧
        if symbol in '([{':
            s.push(symbol)
        # 如果當(dāng)前字符 不是左括號(那當(dāng)前就是右括號)
        else:
            # 并且棧是空的
            if s.isEmpty():
                # 匹配標(biāo)志設(shè)置為 False 表示匹配失敗(孤零零的右括號)
                balanced = False
            # 棧不是空的 拿出棧頂?shù)淖罄ㄌ栠M(jìn)行類型匹配
            else:
                top = s.pop()
                # 類型匹配失敗
                if not matches(top, symbol):
                    balanced = False
        # 索引向后移動(dòng)一位
        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)