【原】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 团队

---

微信号：算法与编程之美