在平時寫程式當中，我們會經常遇到程式當中括號的匹配問題，也就是在程式當中左括號的數量和右括號的數量必須相等，如果不相等的話則程式必然會報錯，Hint:在讀取程式的時候，讀取的結果肯定是左邊的全是左括號，右邊的全是右括號，也就是一定是“(((( )))))”或者“((((((((((((( )))))))))))))))))”的形式，不可能是左右括號互相互動的形式，比如這種：“（）（）（）（）))((())(（”, 撰寫程序式的同學就能夠很輕松的知道這是為什么，因為先有左后有右，正好這個特性和堆疊的特性相符合，因此我們使用堆疊來解決這個問題，首先定義一個堆疊的類class:
class Stack(): def __init__(self): # 初始化一個空的串列 self.__list=[] # 壓堆疊，也就是把元素從上方添加上去，但是這里我咋感覺是從下方添加進去的,順序反了？ def push(self,item): self.__list.append(item) def pop(self): return self.__list.pop()# 彈出堆疊頂的元素,同時洗掉堆疊頂的元素 # 回傳堆疊頂的元素 def peek(self): return self.__list[len(self.__list)-1]# 也就是獲取串列當中的最后一個元素 # 判斷堆疊是否為空 def is_empty(self): return self.__list == [] # 計算堆疊的大小 def size(self): return len(self.__list) #回傳當前堆疊的串列 def what(self): return self.__list
這也是堆疊最常見的定義，已經約定俗成了，現在則是演算法的實作程序，我們可以用程式首先讀取括號，比如已經給定了括號的字串“((((( )))))”，我們將這個字串傳入進行括號匹配的函式當中，如果在回圈讀取括號當中，讀取到了左括號，那么就進行入堆疊操作，之后左括號讀取完畢，再進行右括號的讀取操作，每讀取到一次右括號，則進行出堆疊操作，也就是將之前進堆疊的左括號洗掉，如果左括號比右括號多，那么堆疊無論如何也無法為空，則括號不匹配，回傳false，如果右括號比左括號更多，那么堆疊如果已經為空，程式還在讀取右括號，說明右括號比左括號更多，這樣程式則也回傳false，在左括號和右括號的數量相等的時候，程式回傳True，思路就是這樣的，因此程式的代碼如下：
def pipei(string): stack = Stack() i=0 while i<len(string): if string[i]=="(": stack.push(string[i]) elif string[i]==")": if stack.is_empty(): return False elif not stack.is_empty(): stack.pop() i=i+1 if stack.is_empty(): return True else: return False print("開始括號的匹配問題:") print(pipei("(((())))")) print(pipei("(((()))))))))))"))
輸出為：
開始括號的匹配問題
True
False
那么真實的程式還需要我們自己寫一個讀取程式的檔案，讓我們過濾掉其他符號，只提取出保留括號的字串，我們這里再寫一個函式類實作這個功能：
def tiqukuohao(string): i=0 ls=[] while i<len(string): if string[i]=="(": ls.append(string[i]) elif string[i]==")": ls.append(string[i]) else: pass i=i+1 new_string="".join(ls)#將拿到的串列變成字串，十分常規的操作 return new_string
然后呼叫函式，將一個括號匹配的放入函式，和另一個括號不匹配的字串放入函式：
print(pipei(tiqukuohao("(sdvcsadc(asdasd(a)sdfsdf)asd)asdfas"))) print(pipei(tiqukuohao("sdvcsadc(asdasd(a)sdfsdf)asd)asdfas")))
最后輸出為：
True
False
得解！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/53389.html
標籤：其他
上一篇：flash 頁游是怎么反外掛的