如何解决括号匹配问题
本篇内容主要讲解"如何解决括号匹配问题"，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习"如何解决括号匹配问题"吧!
问题描述
假设我们有一个复杂的字符串，里边包含了多种括号的嵌套，如下图：
这时候人为地用肉眼去判断其中的括号是否匹配是一件非常麻烦的事，不仅耗时耗力，而且准确率极低。那么，有什么方法可以帮助我们高效地进行判断呢，根据栈的特点，我们可以很容易地想到利用python中的list来模拟栈结构进行判断。
示例：
输入：((ABCD(x)
输出：False
输入：{[(rttyy)]sss}
输出：True
解决方案
我们用栈来保存未匹配的左括号，利用for循环从左到右依次遍历字符串的每个元素。当遍历到左括号时，则将其压入栈中；当遍历到右括号时，从栈顶取出一个左括号。如果能够匹配，则继续遍历剩下的字符串。如果遍历的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明该字符串的括号匹配有误，直接返回False。当所有的括号都扫描完成之后，如果栈为空则说明该字符串的括号全部匹配正确，返回True；如果栈不为空，说明有未匹配的左括号，则返回False。
# coding:utf-8 def BracketMatch(str): #把左括号与右括号分别放在一组 LeftBrackets = '{[(' RightBrackets = '}])' #根据括号的匹配关系建立一个字典,右括号当key,左括号当value Brackets = {'}':'{',']':'[',')':'('} # 建立一个栈，初始值为空列表 Stack = [ ] for char in (str): if char in LeftBrackets: Stack.append(char) if char in RightBrackets: if Stack == [ ]: return False else: if Brackets[char] == Stack[-1]: Stack.pop() else: return False if Stack == [ ]: return True else: return False str = input('请输入字符：') print(BracketMatch(str)) |
运行结果如下图：
到此，相信大家对"如何解决括号匹配问题"有了更深的了解，不妨来实际操作一番吧！这里是网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
