数据结构中，用Python 解决各种括号匹配疑难杂症~

Wu_Candy

发布于 2022-07-04 17:56:24

5300

文章被收录于专栏：无量测试之道无量测试之道

本文主要是解决括号匹配的问题。

整体实现思路：借助Python 的List 来实现，因为列表的Append 方法相当于栈的Push 方法即栈的压入，列表的Pop 方法相当于栈的Pop 方法即弹出。

详细的思路：

首先，设置一个字典，用于存放我们要遍历的符号类型。

其次，是设置两个列表分别存放的是各种括号的开括号和闭括号，然后遍历给定的字符串，分如下几种情况：

字符串为空时直接输出True
字符串的符号不成对匹配时输出False
字符串中的符号不是字典中的符号类型时，直接忽略
遍历字符串,将正向的符号压入栈内，遍历到的字符如果是正向符号（正好是最近的一个符号时）的匹配内容就弹出栈

代码实现如下：

#定义要检查匹配的符号类型
brackets = {'}': '{', ']': '[', ')': '(', '>': '<'}
#将符号的正反向进行分类
bracket_l, brackets_r = brackets.values(), brackets.keys()

#定义一个检查字符串的方法
def check(str1):
    alist = [] #定义一个空列表
    for c in str1:
        if c in bracket_l:
            alist.append(c)#将左符号压入栈内
        elif c in brackets_r:#右符号要么出栈，要么匹配失败，不做处理
            if alist and alist[-1] == brackets[c]:#判断alist不会空且alist最后一个字符等于左符号对应的右符号时
                alist.pop() #就做出栈操作
            else:
                return False
    return True #传入空的字符串直接返回true

if __name__ == '__main__':
    print(check("6c[*]{7b +[(8e -s3) * (d4+t5)]}<<>>"))
    print(check("6c*{7b+ [8e- 9f]}<>"))
    print(check(""))

温馨提示：在阅读本文前可以提前看一看栈的上上篇文章《Python 之“栈为何物”》，因为本文是在这篇文章的基础上进行的应用，这里面的实现逻辑非常有意思，同时也体现了算法的精妙之处，值得大家一探究竟。

友情提示：“无量测试之道”原创著作，欢迎关注交流，禁止第三方不显示文章来源时转载。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-09-09，如有侵权请联系 cloudcommunity@tencent.com 删除

python