快捷導(dǎo)航

Python數(shù)據(jù)結(jié)構(gòu)與算法中的棧詳解(2)

更新時(shí)間：2022年03月09日 16:51:07 作者：姜學(xué)遷

這篇文章主要為大家詳細(xì)介紹了Python中的棧，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助

匹配括號(hào)

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

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

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

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

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

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

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

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

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

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

代碼實(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  # 索引 用來(lái)取字符
    # 當(dāng) 索引小于字符串的長(zhǎng)度 并且 匹配標(biāo)志為True 時(shí)
    while index < len(symbolString) and balanced:
        # 取字符串當(dāng)前位的字符
        symbol = symbolString[index]
        # 如果當(dāng)前字符為 左括號(hào) 則入棧
        if symbol == '(':
            s.push(symbol)
        # 如果當(dāng)前字符 不是左括號(hào)(那當(dāng)前就是右括號(hào))
        else:
            # 并且棧是空的
            if s.isEmpty():
                # 匹配標(biāo)志設(shè)置為 False 表示匹配失敗(孤零零的右括號(hào))
                balanced = False
            # 棧不是空的 抵消棧頂?shù)淖罄ㄌ?hào)
            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)前的符號(hào)是左括號(hào)，它就會(huì)被壓入棧中（第27行）。注意第36行，僅通過(guò)pop()將一個(gè)元素從棧頂移除。由于移除的元素一定是之前遇到的左括號(hào)，因此并沒有用到pop()的返回值。在第42~45行，只要所有括號(hào)匹配并且棧為空，函數(shù)就會(huì)返回True ，否則返回False。?

匹配符號(hào)

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

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

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

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

?以下符號(hào)則是不匹配的：

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

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

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

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

代碼實(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  # 索引 用來(lái)取字符
    # 當(dāng) 索引小于字符串的長(zhǎng)度 并且 匹配標(biāo)志為True 時(shí)
    while index < len(symbolString) and balanced:
        # 取字符串當(dāng)前位的字符
        symbol = symbolString[index]
        # 如果當(dāng)前字符屬于 左括號(hào)集 則入棧
        if symbol in '([{':
            s.push(symbol)
        # 如果當(dāng)前字符 不是左括號(hào)(那當(dāng)前就是右括號(hào))
        else:
            # 并且棧是空的
            if s.isEmpty():
                # 匹配標(biāo)志設(shè)置為 False 表示匹配失敗(孤零零的右括號(hào))
                balanced = False
            # 棧不是空的 拿出棧頂?shù)淖罄ㄌ?hào)進(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)，并返回索引。
    # 左右索引對(duì)應(yīng)，表明符號(hào)匹配
    return lefts.index(left) == rights.index(right)

測(cè)試結(jié)果如下圖所示：

在這里插入圖片描述

以上兩個(gè)例子說(shuō)明，在處理編程語(yǔ)言的語(yǔ)法結(jié)構(gòu)時(shí)，棧是十分重要的數(shù)據(jù)結(jié)構(gòu)。幾乎所有記法都有某種需要正確匹配和嵌套的符號(hào)。除此之外，棧在計(jì)算機(jī)科學(xué)中還有其他一些重要的應(yīng)用場(chǎng)景，讓我們繼續(xù)探索。