508，使用栈来判断有效的括号

Original 山大王wld 数据结构和算法 2022-05-19

收录于合集 #算法图文分析 161个

Life is 10% what happens to you and 90% how you react to it.

生活的10%是发生在你身上的事，剩下的90%是你如何应对。

问题描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

使用栈来解决

要判断括号的有效性，左括号必须和右括号相对应。如果是有效括号，并且他们中间还有括号，那么他们必须也是有效的，所以最简单的一种方式就是使用栈来解决。

我们遍历字符串中的所有字符

1，如果遇到了左括号，就把对应的右括号压栈（比如遇到了字符'('，就把字符')'压栈）。

2，如果遇到了右括号

1）查看栈是否为空，如果为空，说明不能构成有效的括号，直接返回false。

2）如果栈不为空，栈顶元素出栈，然后判断出栈的这个元素是否等于这个右括号，如果不等于，说明不匹配，直接返回false。如果匹配，就继续判断字符串的下一个字符。

3，最后如果栈为空，说明是完全匹配，是有效的括号，否则如果栈不为空，说明不完全匹配，不是有效的括号。

这里随便举个例子比如字符串是“{([]())}”，画个图来看一下。

代码如下

 1public boolean isValid(String s) {
 2    Stack<Character> stack = new Stack<>();
 3    char[] chars = s.toCharArray();
 4    //遍历所有的元素
 5    for (char c : chars) {
 6        //如果是左括号，就把他们对应的右括号压栈
 7        if (c == '(') {
 8            stack.push(')');
 9        } else if (c == '{') {
10            stack.push('}');
11        } else if (c == '[') {
12            stack.push(']');
13        } else if (stack.isEmpty() || stack.pop() != c) {
14            //否则就只能是右括号。
15            //1，如果栈为空，说明括号无法匹配。
16            //2，如果栈不为空，栈顶元素就要出栈，和这个右括号比较。
17            //如果栈顶元素不等于这个右括号，说明无法匹配，
18            //直接返回false。
19            return false;
20        }
21    }
22    //最后如果栈为空，说明完全匹配，是有效的括号。
23    //否则不完全匹配，就不是有效的括号
24    return stack.isEmpty();
25}