在考慮這個問題前,我們首先復習數(shù)據(jù)結構中的棧,因為編譯器中括號匹配就是通過棧來實現(xiàn)的:

成都創(chuàng)新互聯(lián)長期為上千家客戶提供的網(wǎng)站建設服務，團隊從業(yè)經驗10年，關注不同地域、不同群體，并針對不同對象提供差異化的產品和服務；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為葫蘆島企業(yè)提供專業(yè)的成都網(wǎng)站設計、網(wǎng)站建設，葫蘆島網(wǎng)站改版等技術服務。擁有十多年豐富建站經驗和眾多成功案例,為您定制開發(fā)。

棧:

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

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

#建立棧結構 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，

這個問題可以說非常重要,因為我們程序編譯器中常常要檢查括號是否配對,如果我們能夠真正了解這個原理,能夠有助于我們深入了解編譯器原理:

我們首先考慮簡單的情況:當所有括號類型相同的時候,我們只需要讓每個左括號都有一個右括號與其匹配就可以,總結來說,我們將左括號計數(shù)(left)有如下公式:

left++left++left++

我們考慮遇到右括號時,left的不同情況:

left=0 說明沒有和右括號相匹配的左括號,即表達式是invaild

left>0,我們有與右括號相匹配的左括號,此時匹配我們要將left??left--left??

如果遍歷完所有的符號后,left!=0，說明表達式依舊是invalid

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

({)}

進一步考慮

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

關于有效括號表達式的一個有趣屬性是有效表達式的子表達式也應該是有效表達式。(不是每個子表達式)。

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

遇到左括號將其壓入棧。

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

如果最后棧空就說明了,表達式有效，代碼如下,用字典的數(shù)據(jù)結構有助于我們降低復雜度:

#建立棧結構 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_)

總結

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

遇到左括號將其壓入棧。

遇到右括號,將棧頂推出,如果與棧頂相匹配,繼續(xù)進行,如果不匹配,則可以判斷整個表達式無效(invaild)