python括号配对检测问题_python应用-括号匹配问题（栈的应用）

每种括号都是由一个开括号和一个闭括号组成。括号的嵌套应能正确的匹配，如((()))。不难看出括号配对的原则是在扫描过程中，遇到的闭括号应该与此前最近遇到且尚未获得匹配的开括号配对，如果最近的未匹配开括号和当前闭括号不配对，或者找不到这样的开括号，就是匹配失败。

由于括号的嵌套，需要逐对匹配。当前闭括号应该与前面最近的尚未匹配的开括号匹配，下一个闭括号应与前面次括号匹配。这说明，需要存储开括号的使用规则是后存入的先使用。进而如果一个开括号已经配对，就应该删除这个括号，为随后的匹配做准备。显然，在扫描过程中，后遇到并保存的开括号将先配对并被删除，这就是按出现的顺序后进先出。

基于以上分析，很容易想到使用堆栈实现，python代码为

def fun(str1):

length=len(str1)

cnt=0

for i in range(length):

if str1[i]=='(':

cnt+=1           #模拟压栈

elif str1[i]==')':

if cnt>0:

cnt-=1        #模拟出栈

else:

return False

else:

return False

测试用例

>>> fun("()")

True

>>> fun("())")

False

>>> fun("())(")

False

>>> fun("()((")

False

>>>

对上述问题稍微扩展一下，要求对()、{}、[]进行匹配。这时需要用一个变量保存这个匹配关系。利用栈结构，遍历字符串，遇到(、{、[字符时压栈，遇到)、}、]时出栈，出栈的字符要与)、}、]相匹配。若都匹配，则最终栈为空。

def mymatch(astr):

length=len(astr)

if length % 2 !=0:

return "stris invalid"

blist=[]

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

i=0

while i<=length-1:

if astr[i] instrdict.keys():

blist.append(astr[i])        #入栈

if astr[i] instrdict.values():

if blist!=[]:

anystr=blist.pop()      #出栈

ifstrdict[anystr] !=astr[i]:

return False

else:

returnFalse

i+=1

#print blist

if blist == []:

return True

return False

测试用例

>>>mymatch('))')

False

>>>

>>>mymatch('({})')

True

>>>mymatch('({[()]})')

True