判断各种括号的有效使用

欢迎点击「算法与编程之美」关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

问题描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：

1.左括号必须用相同类型的右括号闭合。

2.左括号必须以正确的顺序闭合。

解决方案

思路：首先我们要讲我们输入的字符串中的括号提取出来到一个列表，然后判断是奇数个还是偶数个，奇数个一定不符合；如果是偶数，再遍历所有元素，因为括号在一起，通过以i和i+1的形式来确定符合的括号，再通过切片将符合的全部切去，将最后剩下的再来判断，将三种符号放入列表中，如果剩下的大于2个就无效，如果是两个并且在了列表中就有效。

首先我们通过一个for循环将我们输入的这个字符串中的括号提取出来，以通过建一个包含这些括号的列表然后挨个挨个的循环看是否每个元素属于这个列表，最后得到一个只含括号的列表，再将其转化为一个字符串然后进行后面的操作。

先判断是否为奇数个

如果这里为奇数个，就直接判断无效并且退出程序，因为符号一定是一一对应，奇数个便不能对应.如果为偶数，则跳开进入下面的程序。

这里是在个数为偶数的情况下，先遍历所有的符号元素，然后加一个for循环，同时a,b,c分别是我们想要在这个字符串中判断的依据，代码意思是一组符号总是相邻存在。先设定好条件，然后再进行接下来的步骤。

这里，上面三个条件在for循环下随便满足一个就进行切片处理，将满足的两个符号前后的所有元素进行切片然后组合，就得到除去这组元素的另一个字符串。一直循环，直到没有满足条件的就跳出循环。

然后接下来对剩下的进行判断，如果多余两个剩下，那就说明有多个未切片成功，就一定有相邻不匹配的，那么这个字符串无效。如果最后只剩下两个的话，我们不妨先设出一个包含3组正确顺序的列表，然后将我们切片剩下的字符串拿来比，如果剩下的在我们设的列表中的话，那么就说明是有效的，反之无效。

结语

解决字符串中类似循环删除问题的时候，我们可以利用切片，合并的功能。还有看到题目时一定要考虑有没有简单直接的方法能够帮忙理解，如本题的奇数个就可以直接判断出来。

实习编辑 | 王楠岚

责 编 | 李和龙