如何解決括號(hào)匹配問題

發(fā)布時(shí)間：2021-10-09 16:13:14 來源：億速云閱讀：176 作者：iii 欄目：編程語言

本篇內(nèi)容主要講解“如何解決括號(hào)匹配問題”，感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“如何解決括號(hào)匹配問題”吧!

問題描述

假設(shè)我們有一個(gè)復(fù)雜的字符串，里邊包含了多種括號(hào)的嵌套，如下圖：

如何解決括號(hào)匹配問題

這時(shí)候人為地用肉眼去判斷其中的括號(hào)是否匹配是一件非常麻煩的事，不僅耗時(shí)耗力，而且準(zhǔn)確率極低。那么，有什么方法可以幫助我們高效地進(jìn)行判斷呢，根據(jù)棧的特點(diǎn)，我們可以很容易地想到利用python中的list來模擬棧結(jié)構(gòu)進(jìn)行判斷。

示例：

輸入：((ABCD(x)

輸出：False

輸入：{[(rttyy)]sss}

輸出：True

解決方案

我們用棧來保存未匹配的左括號(hào)，利用for循環(huán)從左到右依次遍歷字符串的每個(gè)元素。當(dāng)遍歷到左括號(hào)時(shí)，則將其壓入棧中；當(dāng)遍歷到右括號(hào)時(shí)，從棧頂取出一個(gè)左括號(hào)。如果能夠匹配，則繼續(xù)遍歷剩下的字符串。如果遍歷的過程中，遇到不能配對(duì)的右括號(hào)，或者棧中沒有數(shù)據(jù)，則說明該字符串的括號(hào)匹配有誤，直接返回False。當(dāng)所有的括號(hào)都掃描完成之后，如果棧為空則說明該字符串的括號(hào)全部匹配正確，返回True；如果棧不為空，說明有未匹配的左括號(hào)，則返回False。

# coding:utf-8

def BracketMatch(str):

#把左括號(hào)與右括號(hào)分別放在一組

LeftBrackets = '{[('

RightBrackets = '}])'

#根據(jù)括號(hào)的匹配關(guān)系建立一個(gè)字典,右括號(hào)當(dāng)key,左括號(hào)當(dāng)value

Brackets = {'}':'{',']':'[',')':'('}

# 建立一個(gè)棧，初始值為空列表

Stack = [ ]

for char in (str):

if char in LeftBrackets:

Stack.append(char)

if char in RightBrackets:

if Stack == [ ]:

return False

else:

if Brackets[char] == Stack[-1]:

Stack.pop()

else:

return False

if Stack == [ ]:

return True

else:

return False

str = input('請(qǐng)輸入字符：')

print(BracketMatch(str))

運(yùn)行結(jié)果如下圖：

到此，相信大家對(duì)“如何解決括號(hào)匹配問題”有了更深的了解，不妨來實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！

向AI問一下細(xì)節(jié)

如何解決括號(hào)匹配問題

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽