問題描述：

給定一個字符串文字，里面可能含有"()","[]","{}"三種
括號，判斷字符串中的括號是否都成對出現(xiàn)***

思路分析：

如果括號正確匹配，肯定滿足：
1、一對正確匹配的括號，一定先出現(xiàn)左括號，再出現(xiàn)右括號；
2、三種括號不會出現(xiàn)交叉現(xiàn)象。如“{【】{}（）（）}”，而不會出現(xiàn)類似“（【）】”的情況。

如果以人類思維方式取匹配，過程如下：
遇到左括號先暫時不管，遇到右括號再看前面出現(xiàn)的左括號是否匹配。（而且由于括號不會交叉，遇到右括號后，查找的一定是距離最近的一個左括號）

最前面（最先）出現(xiàn)的左括號最后比較，最近出現(xiàn)的左括號先比較。因此，我們可以考慮利用棧“先進后出”的特性。

當遇到一個左括號，讓它入棧；遇到一個右括號，則比較棧頂元素是否與之匹配。

首先創(chuàng)建一個Stack類

class Stack:def __init__(self):self.__list = [] # 初始化列表，存儲棧中元素。因為不需要外界訪問，所以私有化。def push(self, item): # 彈出棧頂元素self.__list.append(item)def peek(self):return self.__list[len(self.__list) - 1]def pop(self):return self.__list.pop() # 列表的pop方法，默認返回最后一個元素 def is_empty(self): # 判斷是否棧空return self.__list == []

遇到右括號，如何表示棧頂元素與括號“匹配”呢？*
一種思路是用字典鍵值對先存儲對應(yīng)的匹配關(guān)系

def is_matched_brackets(text):'''判斷括號是否匹配:param text: 字符串類型:return: True --> 全部匹配; False --> 不匹配'''dict_bracket = {')': '(', ']': '[', '}': '{'} # 用字典的鍵值對存儲匹配關(guān)系s = Stack() # 創(chuàng)建一個棧對象，存儲左括號for i in text:if i in dict_bracket.values(): # 左括號入棧 s.push(i)elif i in dict_bracket: # 遇到右括號if s.is_empty(): # 棧空，說明剩余右括號未匹配print('missing left bracket')return Falseif s.peek() != dict_bracket[i]: # 如果括號不匹配print('unmatched bracket')return Falses.pop() # 如果括號匹配則將左括號出棧if not s.is_empty(): # 循環(huán)結(jié)束。棧中還有元素，說明少右括號print('missing right bracket')return Falsereturn True

以上代碼可以初步判斷括號是否匹配。但如果想要更加精確的把未匹配的地方告訴用戶，我們可以進一步判斷未匹配括號的位置及括號的符號

我們只需在上述代碼的基礎(chǔ)上將左括號的索引位置以及括號一起存儲到棧中即可
代碼如下：

# 如果需要知道具體哪個位置的括號沒有匹配 def is_matched_brackets2(text):dict_bracket = {')': '(', ']': '[', '}': '{'}s = Stack() # 創(chuàng)建一個棧對象，存儲左括號for i in range(len(text)):if text[i] in dict_bracket.values(): # 左括號入棧s.push((i, text[i])) # 因為最后要記錄剩余左括號未匹配的情況，所以索引也要存儲elif text[i] in dict_bracket: # 遇到右括號if s.is_empty() or s.peek()[1] != dict_bracket[text[i]]: # 棧空和缺少對應(yīng)左括號可以歸為一種情況print('unmatched right bracket {} at {}'.format(text[i], i))return Falses.pop() # 右括號匹配時，將左括號出棧if not s.is_empty():index, item = s.pop()print('unmatched left bracket {} at {}'.format(item, index))return Falsereturn True

在此次練習(xí)中，我有幾個細節(jié)方面的問題，總結(jié)如下：
1、if i in dict_bracket.values():
第一次忘記寫values后面的括號，報錯為:
TypeError: argument of type ‘builtin_function_or_method’ is not iterable*

>>> dict_ = {1:'a',2:'b'} >>> dict_.values <built-in method values of dict object at 0x0000028ECFC9F500> >>> type(dict_.values) <class 'builtin_function_or_method'>

調(diào)用內(nèi)置方法，需要加括號

2、

if text[i] in dict_bracket.values: # 遇到左括號入棧s.push((i, text[i]))

因為push函數(shù)的本質(zhì)是調(diào)用列表的append()方法（見上文），所以傳入的對象應(yīng)該是一個整體。 s.push((i, text[i])) 內(nèi)層括號將索引與括號符號一一個元組形式傳遞。

3、

if s.peek() != dict_bracket[i]: # 如果括號不匹配print('unmatched bracket')

這個地方只能用peek()判斷—查看棧頂元素，
不能用pop（）— 彈出棧頂元素
否則括號不匹配，棧頂元素也被取出來

4、

if s.is_empty() or s.peek()[1] != dict_bracket[text[i]]:# [1]表示對棧中元素（元組類型）索引，返回括號符號index, item = s.pop() # 左邊逗號分隔，python自動生成元組

5、第一次嘗試用if判斷時

for i in text:if i is '(': # 左括號入棧s.push(i)

報錯為：
SyntaxWarning: “is” with a literal. Did you mean “==”?

is 是身份運算符，本質(zhì)是通過id()函數(shù)比較的。我進行了以下嘗試：

a = '(df' for i in a:print(i is '(')

運行結(jié)果：True False False
也就是說，a[0] is ‘(’ 這個判斷是沒有問題的
這個問題是我所感到疑惑，尚未解決的。

總結(jié)

以上是生活随笔為你收集整理的python用栈实现括号匹配问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。