快捷導(dǎo)航

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

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

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

題目描述

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

有效字符串需滿足：

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

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

測(cè)試用例

示例 1

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

示例 2

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

示例 3

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

示例 4

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

示例 5

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

代碼實(shí)現(xiàn)

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

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

class Solution:
    def isValid(self, s: str) -> bool:
        #如果字符串是奇數(shù)一定不滿足條件
        if len(s) % 2 != 0:
            return False
        #定義一個(gè)括號(hào)字典
        bracket_dict = {")":"(","]":"[","}":"{"}
        #定義一個(gè)棧
        stack = []
        for c in s:
            #當(dāng)匹配到括號(hào)的結(jié)束符時(shí)
            if c in bracket_dict:
                #棧不能為空,并且棧頂要與結(jié)束的括號(hào)匹配
                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詳解