python實現(xiàn)有效的括號判斷實例代碼

更新時間：2022年01月27日 10:30:52 作者：修煉之路

這篇文章主要給大家介紹了關(guān)于python實現(xiàn)有效的括號判斷的相關(guān)資料,文中通過實例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下

題目描述

給定一個只包括 '(',')','{','}','[',']'的字符串 s ，判斷字符串是否有效。

有效字符串需滿足：

左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。

LeetCode原題地址：https://leetcode-cn.com/problems/valid-parentheses/

測試用例

示例 1

輸入：s = “()”
輸出：true

示例 2

輸入：s = “()[]{}”
輸出：true

示例 3

輸入：s = “(]”
輸出：false

示例 4

輸入：s = “([)]”
輸出：false

示例 5

輸入：s = “{[]}”
輸出：true

代碼實現(xiàn)

實現(xiàn)這個算法我們可以利用棧的先進后出的特性，對于每個括號它需要找到與它匹配的括號。

我們先遍歷字符串，將字符串的字符存入到棧中，當匹配到結(jié)束的括號時，如果此時棧不為空并且棧頂?shù)淖址c當前的括號相匹配時，我們將棧頂?shù)淖址M行出棧操作，否則直接返回False。如果最終棧為空表示每個括號都找到了匹配的結(jié)束括號，否則匹配失敗。

class Solution:
    def isValid(self, s: str) -> bool:
        #如果字符串是奇數(shù)一定不滿足條件
        if len(s) % 2 != 0:
            return False
        #定義一個括號字典
        bracket_dict = {")":"(","]":"[","}":"{"}
        #定義一個棧
        stack = []
        for c in s:
            #當匹配到括號的結(jié)束符時
            if c in bracket_dict:
                #棧不能為空,并且棧頂要與結(jié)束的括號匹配
                if len(stack) > 0 and bracket_dict[c] == stack[-1]:
                    stack.pop()
                else:
                    return False
            else:
                stack.append(c)
        return not stack

s = Solution()
print(s.isValid("()[]{}"))
print(s.isValid("([)]"))

參考：LeetCode詳解