Python|用“栈”的方法完成括号匹配

问题描述

使用“栈”的方法完成括号匹配（给定一个字符串，判断字符串里的括号是否有效。）

正确匹配情况：（1）[](){} ；（2）([{}])

解决方案

先遍历字符串把三对括号提出来，再利用‘栈’把左括号一个个的放入其中并且遍历到右括号立即进行匹配。匹配成功后删除‘栈’中的左括号并继续，匹配失败则返回‘False’.最后返回栈的长度，避免出现奇数个括号的错误。

注意：不可以把左括号全部放入一个‘栈’，右括号全部放入另一个‘栈’。然后进行匹配。

例如：“([{}])”和“([}{])”左右括号分别放入两个栈的情况都是“([{”和“}])”,但是前一个是正确的，后一个是错误的。

实现代码：

def zhan(s):

#新建一个列表，存放括号，出掉非括号的字符

q = []

for i in s:

if i == '(' or i == ')' or i == '[' or i == ']' or i == '{' or i == '}' :

q.append(i)

#利用栈匹配括号

l = []

for i in q:

if i == '(' or i == '[' or i == '{': l.append(i)

elif i == ')' and l[-1] == '(': l.pop()

elif i == ']' and l[-1] == '[': l.pop()

elif i == '}' and l[-1] == '{': l.pop()

return len(l) == 0

s = "题中字符串"

result = zhan(s)

print(result)

END主       编   |   王文星

责       编   |   周茂林

where2go 团队

微信号：算法与编程之美