Hi，大家好，我是Tom。一个美术生转到Java开发的程序员。今天给大家分享的是力扣题第20题，有效的括号。在解题过程中，也会手写一些伪代码。当然，如果想要完整的源码的话，可以到我的个人主页简介中获取。
这道题呢比较简单，但是曾经成为B站的算法面试题，而且通过率只有44.5%。
1、题干分析
首先，我们还是来分析一下这道题的题干。
它说，给定你一个只包括圆括号、花括号或者方括号的这么一个字符串，让你判断这个字符串是否有效。那这个字符串有效需要满足什么条件呢？
第一个条件是：左括号必须要有相同类型的右括号闭合。什么意思呢？就是它必须是一个有效的括号，比如说这样 （ ）是一个有效的括号，那这样 ) ( 就不是一个有效的括号，当然，这样 （ ] 也不是一个有效的括号。
第二个条件是：左括号必须以正确的顺序闭合，那也就是跟上面描述的意思相同。
第三个条件是：说每个右括号都应该有一个相同类型的左括号对应。跟上面的意思也一样。
官方呢，也给了几个示例，我们来看一下：
输入左圆括号和右圆括号，输出结果为 true ，那么输入 左圆括号 和 右方括号，输出结果为 false。
对于这道题呢，它是为压栈这种方法而设计的。所以，我今天这道题呢，我给大家只讲一种解法，也就是压栈法求解。
2、压栈法求解
接下来，老规矩，我们先来看用压栈法求解的解题思路。假设我们输入这样一个字符串（（ ）） [ ] ，一对圆括号中包含一对圆括号，然后外加一对方括号，我们一眼看上去显然是一对有效的括号。但是我们人能够一眼识别出来是有效的，不代表程序一眼就能看出来。所以，我们得有一个算法告诉我们的程序，如何来判断括号是有效的。
在这里，我们可以准备一个栈来做辅助。首先，我们需要从头到尾遍历一次这个字符串中的字符。在遍历的过程中，我们只要发现它是左边的括号（不管它是圆括号、花括号还是方括号，只要是左边的括号）就把它push到栈里来，这叫压栈。
比如说，我们往下遍历第一个是左圆括号，把它push到栈里来，第二个还是左圆括号，继续把它push到栈里面来。
再往下移发现是右圆括号，那这个时候我们应该怎么办呢？我们回顾一下，栈有什么特点？先入后出的特点，那我们来看，第一个进来的是左圆括号，压在栈底。第二个进来的也是左圆括号，目前压在栈顶。那如果我现在pop这个栈的话，第一个出来的应该最后push进来的值。
所以，我们遇到右括号，就把栈顶的值pop出来，那这个时候，我们发现右圆括号和栈顶的左圆括号是能够匹配的。于是，我们的遍历就可以接着往下走，继续拿到的值为右圆括号，这个时候我要继续pop这个栈，此时，取出的值为左圆括号，正好又能和右圆括号匹配。
于是，我们的遍历就继续往下走，继续拿到的值为左方括号，此时，我们就压栈。而这个时候，栈里面的全部已经pop完了，所以，左方括号这个时候又压到了栈底。
然后，继续放下遍历。我们又得到了一个右括号。遇到右括号要pop这个栈，此时，取出的值为左方括号，正好能跟右方括号匹配上。
前面的每一步遍历都成功匹配了，直到遍历完成。那么最后，我们只需要判断这个栈是不是为空，如果为空，说明所有括号都是有效匹配，返回为true。
比如说，我们是输入是这个字符串后面再加一个花括号。那这个时候遍历完成的时候，发现栈中值不为空，栈的花括号没有可以跟它匹配值了，这个时候就应该返回false。
当然，如果遇到右括号，从栈中pop出来的值不能和右括号匹配的，就直接终止遍历返回false，因为，再往下遍历已经没有意义了。
所以说，有效的括号它们都是情侣，要成双成对地出现，不会有多余的单身狗，也不会有不同类型括号谈恋爱，比如小倩和宁采臣，人妖相恋也不符合人伦。
下面来看一下压栈法解法的伪代码。
以上就是我关于有效的括号这道题的解题思路分享。这道题的算法很简单，主要是考核栈这种数据结构，当遇到左括号的时候，就做压栈操作，遇到右括号的时候，就将栈顶的元素做出栈操作，并且判断是否匹配。
我是被编程耽误的文艺Tom，如果我的分享对你有帮助，请动动手指一键三连分享给更多的人。关注我，面试不再难！
附：完整源码地址：
GitHub
GitEE
