算法

數據結構

數據結構和算法(Python版)：利用棧(Stack)實現括號的匹配問題

在平時寫程序當中，我們會經常遇到程序當中括號的匹配問題，也就是在程序當中左括號的數量和右括號的數量必須相等。如果不相等的話則程序必然會報錯。Hint:在讀取程序的時候，讀取的結果肯定是左邊的全是左括號，右邊的全是右括號，也就是一定是“(((( )))))”或者“((((((((((((( )))))))))))))))))”的形式，不可能是左右括號互相交互的形式，比如這種：“()()()()))((())((”, 編寫過程序的同學就能夠很輕松的知道這是為什么，因為先有左后有右，正好這個特性和棧的特性相符合，因此我們使用棧來解決這個問題，首先定義一個棧的類class:

classStack():def __init__(self):#初始化一個空的列表

self.__list=[]#壓棧，也就是把元素從上方添加上去，但是這里我咋感覺是從下方添加進去的,順序反了？

defpush(self,item):

self.__list.append(item)defpop(self):return self.__list.pop()#彈出棧頂的元素,同時刪除棧頂的元素

#返回棧頂的元素

defpeek(self):return self.__list[len(self.__list)-1]#也就是獲取列表當中的最后一個元素

#判斷棧是否為空

defis_empty(self):return self.__list ==[]#計算棧的大小

defsize(self):return len(self.__list)#返回當前棧的列表

defwhat(self):return self.__list

這也是棧最常見的定義，已經約定俗成了。現在則是算法的實現過程，我們可以用程序首先讀取括號，比如已經給定了括號的字符串“((((( )))))”，我們將這個字符串傳入進行括號匹配的函數當中。如果在循環讀取括號當中，讀取到了左括號，那么就進行入棧操作。之后左括號讀取完畢，再進行右括號的讀取操作，每讀取到一次右括號，則進行出棧操作，也就是將之前進棧的左括號刪除。如果左括號比右括號多，那么棧無論如何也無法為空，則括號不匹配，返回false。如果右括號比左括號更多，那么棧如果已經為空，程序還在讀取右括號，說明右括號比左括號更多，這樣程序則也返回false。在左括號和右括號的數量相等的時候，程序返回True，思路就是這樣的，因此程序的代碼如下：

defpipei(string):

stack=Stack()

i=0while i

stack.push(string[i])elif string[i]==")":ifstack.is_empty():returnFalseelif notstack.is_empty():

stack.pop()

i=i+1

ifstack.is_empty():returnTrueelse:returnFalseprint("開始括號的匹配問題:")print(pipei("(((())))"))print(pipei("(((()))))))))))"))

輸出為：

開始括號的匹配問題

True

False

那么真實的程序還需要我們自己寫一個讀取程序的文件，讓我們過濾掉其他符號，只提取出保留括號的字符串，我們這里再寫一個函數類實現這個功能：

deftiqukuohao(string):

i=0

ls=[]while i

ls.append(string[i])elif string[i]==")":

ls.append(string[i])else:passi=i+1new_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

得解！

內容來源于網絡，如有侵權請聯系客服刪除