【原】算法创作|栈的应用——括号匹配问题解决方法

问题描述

假设我们有一个复杂的字符串，里边包含了多种括号的嵌套，如下图：

这时候人为地用肉眼去判断其中的括号是否匹配是一件非常麻烦的事，不仅耗时耗力，而且准确率极低。那么，有什么方法可以帮助我们高效地进行判断呢，根据栈的特点，我们可以很容易地想到利用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))

运行结果如下图：

结语

此题难度一般，最关键的是要理解栈结构的特点，就是后进先出，了解了栈的特点后再运用遍历和嵌套判断便可解决这个问题。当然，这只是其中一种解决办法，我们只有通过不断地学习才能写出更优的算法和代码。

实习编辑：王晓姣

作者：唐雷清，祝菱晞，刘紫轩

稿件来源：深度学习与文旅应用实验室（DLETA）