Leetcode 之判斷字符串是否有效及棧結(jié)構(gòu)

　　在考慮這個(gè)問題前,我們首先復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)中的棧,因?yàn)榫幾g器中括號(hào)匹配就是通過棧來實(shí)現(xiàn)的:

　　棧:

　　棧：是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu);其本質(zhì)也就有特殊限制的鏈表(先進(jìn)后出,棧頂),提起棧我們首先會(huì)想到什么呢?當(dāng)然是進(jìn)棧(push)和出棧(pop),下面我們通過代碼來實(shí)現(xiàn)進(jìn)棧和出棧過程:

　　我們要重視棧頂這個(gè)部分:棧頂(top),我們要保證棧頂只有一個(gè)節(jié)點(diǎn),并且鏈接到下面的節(jié)點(diǎn),具體的實(shí)現(xiàn)方式是,構(gòu)建一個(gè)新節(jié)點(diǎn),把新節(jié)點(diǎn)的next(指針)指向原先的棧頂,再把棧頂設(shè)置為新節(jié)點(diǎn)。如下面代碼所示。

　　#建立棧結(jié)構(gòu) push 和 pop

　　#首先定義listnode

　　class node(object):

　　def __init__(self,value=None):

　　self.value=value

　　self.next=None

　　class stack(object):

　　def __init__(self):

　　self.node=node()

　　self.top=[self.node]

　　def push(self,elem):

　　new_node=node(elem)

　　if self.top[0].value==None:

　　new_node.next=None

　　else:

　　new_node.next=self.top[0]

　　self.top.append(new_node)

　　self.top.pop(0)

　　def pop(self):

　　try:

　　value_top=self.top[0].value

　　node=self.top[0].next

　　self.top.append(node)

　　self.top.pop(0)

　　return value_top

　　except:

　　print('wrong')

　　s=stack()

　　for i in ['a','b','c','d']:

　　s.push(i)

　　for i in range(4):

　　print(s.pop())

　　問題和問題分析

　　問題來源于leetcode，

　　這個(gè)問題可以說非常重要,因?yàn)槲覀兂绦蚓幾g器中常常要檢查括號(hào)是否配對(duì),如果我們能夠真正了解這個(gè)原理,能夠有助于我們深入了解編譯器原理:

　　我們首先考慮簡(jiǎn)單的情況:當(dāng)所有括號(hào)類型相同的時(shí)候,我們只需要讓每個(gè)左括號(hào)都有一個(gè)右括號(hào)與其匹配就可以,總結(jié)來說,我們將左括號(hào)計(jì)數(shù)(left)有如下公式:

　　left++left++left++

　　我們考慮遇到右括號(hào)時(shí),left的不同情況:

　　left=0 說明沒有和右括號(hào)相匹配的左括號(hào),即表達(dá)式是invaild

　　left>0,我們有與右括號(hào)相匹配的左括號(hào),此時(shí)匹配我們要將left??left--left??

　　如果遍歷完所有的符號(hào)后,left!=0，說明表達(dá)式依舊是invalid

　　總而言之,我們只需要計(jì)數(shù)左括號(hào),看是否有與之匹配的右括號(hào),但是這僅僅是簡(jiǎn)單的情況,沒有考慮到不同符號(hào)之間的相對(duì)位置,如果是如下這樣的表達(dá)式,我們上面總結(jié)的規(guī)律就不滿足了:

　　({)}

　　進(jìn)一步考慮

　　根據(jù)一個(gè)有趣的規(guī)律:鄭州婦科醫(yī)院 http://www.ytsgfk120.com/

　　關(guān)于有效括號(hào)表達(dá)式的一個(gè)有趣屬性是有效表達(dá)式的子表達(dá)式也應(yīng)該是有效表達(dá)式。(不是每個(gè)子表達(dá)式)。

　　從這里我們看出是遞歸的,也就是如果每個(gè)子表達(dá)式是有效的表達(dá)式,整個(gè)表達(dá)式就是有效的,這樣我們就可以從解決每個(gè)子表達(dá)式出發(fā),當(dāng)表達(dá)式匹配就刪除,直至剩下空的表達(dá)式說明了表達(dá)式是有效的:算法流程如下:

　　遇到左括號(hào)將其壓入棧。

　　遇到右括號(hào),將棧頂推出,如果與棧頂相匹配,繼續(xù)進(jìn)行,如果不匹配,則可以判斷整個(gè)表達(dá)式無效(invaild)。

　　如果最后?？站驼f明了,表達(dá)式有效，代碼如下,用字典的數(shù)據(jù)結(jié)構(gòu)有助于我們降低復(fù)雜度:

　　#建立棧結(jié)構(gòu) push 和 pop

　　#首先定義listnode

　　class node(object):

　　def __init__(self,value=None):

　　self.value=value

　　self.next=None

　　class stack(object):

　　def __init__(self):

　　self.top=None

　　def push(self,elem):

　　new_node=node(elem)

　　if self.top==None:

　　new_node.next=None

　　else:

　　new_node.next=self.top

　　self.top=new_node

　　def pop(self):

　　if self.top!=None:

　　value_top=self.top.value

　　node=self.top.next

　　self.top=node

　　return value_top

　　else:

　　return False

　　string='()'

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

　　def judge_str(str_,dict_):

　　s=stack()

　　for i in str_:

　　if i in dict_:

　　result=s.pop() if s.top else '#'

　　if (result!=dict_[i]):

　　return False

　　else:

　　s.push(i)

　　if s.top==None:

　　return True

　　else:

　　return False

　　judge_str(string,dict_)

　　總結(jié)

　　總結(jié)而言,我們括號(hào)匹配是一種遞歸結(jié)構(gòu),如果每個(gè)子表達(dá)式匹配,那么整個(gè)表達(dá)式也匹配,用棧結(jié)構(gòu)來實(shí)現(xiàn)它,按照以上總結(jié)的規(guī)律，用字典格式可以很快很好的解決問題.

　　遇到左括號(hào)將其壓入棧。

　　遇到右括號(hào),將棧頂推出,如果與棧頂相匹配,繼續(xù)進(jìn)行,如果不匹配,則可以判斷整個(gè)表達(dá)式無效(invaild)