日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

Python數據結構與算法中的棧詳解(2)_python

作者：姜學遷 ? 更新時間： 2022-05-09 編程語言

匹配括號

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

比如我們都寫過這樣所示的算術表達式， ( 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)

測試結果如下圖所示：

在這里插入圖片描述

以上兩個例子說明，在處理編程語言的語法結構時，棧是十分重要的數據結構。幾乎所有記法都有某種需要正確匹配和嵌套的符號。除此之外，棧在計算機科學中還有其他一些重要的應用場景，讓我們繼續探索。

總結

原文鏈接：https://blog.csdn.net/jiang1126/article/details/123268956

欄目分類
最近更新