力扣leetcode题目分析——有效的括号

超、凢脫俗 2024-04-18 14:51 74阅读 0赞

## 题目 ##

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

有效字符串需满足：

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

注意：空字符串可被认为是有效字符串。  
**示例**

> 输入: “()”  
> 输出: true

> 输入: “()\[\]\{\}”  
> 输出: true

> 输入: “(\]”  
> 输出: false

> 输入: “(\[)\]”  
> 输出: false

> 输入: “\{\[\]\}”  
> 输出: true

## 链接 ##

https://leetcode-cn.com/problems/valid-parentheses/

## 运行环境 ##

java语言

## 说明 ##

现在我来写一个高赞的答案，因为我自己写完之后发现自己写的真的很不简洁，虽然和高赞答案的思路一样，但是写出来就是没有人家那么简洁明了。所以还是不献丑了，说一下高赞答案吧。至于为什么我的思路会和高赞答案一样，原因在于我的老师的思路和高赞答案一样，以前学习数据结构的时候，这是我们当时的一道练习题，当时我特别差，只能理解思路，不会写。现在看到这道题觉得好亲切，虽然学数据结构的时候用的是C语言，但是思路一点没变，看到这道题就想到当初在学栈的时候，哈哈，突然很想去翻一下之前的笔记本，看看我当初是怎么记的。下面说一下思路吧，虽然脑子里知道是这样做，但是要把思路讲清楚真的难。

## 思路 ##

首先想一下什么是有效的括号，题目中有效的括号就是指能成功配对并且如果括号中还有括号，那么括号中的括号也要配对。这里采用栈来判断：我们将括号进栈，如果进栈的元素是‘（’或‘\['或’\{’，那就先存起来，看看后面有没有可以与之配对的。最先进栈的元素肯定是第一个字符，如果最先进栈的元素是‘）’或‘\]’或‘\}’，说明肯定不正确，但是如果‘）’或‘\]’或‘\}’不是第一个进栈，那么我们就要去栈里面取最近的一个元素看能不能配对，如果不行，说明不是有效的括号，如果可以，那么我就把与之配对的那个元素退栈，再看下一个元素是什么，如果最后括号都能配对的话，那栈中肯定已经没有元素了，所以通过判断栈的元素是否为0就可以知道是否是有效的括号，同时空字符串也可以是有效的括号。  
分为下面几种情况：  
1.栈为空时，循环到左括号，进栈；循环到右括号，false  
2.栈不为空时，循环到左括号，进栈；循环到右括号，从栈中取最后存进去的元素配对，配对成功，将栈中的一个元素退栈；配对不成功，false；  
3.直到循环完毕，栈中没有元素，true

**示例**

> 输入: “()\[\]\{\}”  
> 输出: true

输入的是 “()\[\]\{\}”，过程为：  
1.最开始栈中没有元素，‘（’是左括号，将‘（’进栈  
2.‘）’是右括号，取栈最后存进去的元素‘（’与‘）’判断，可以配对，将‘（’退栈  
3.栈空，‘\[’是左括号，将‘\[’进栈  
4.‘\]’是右括号，取栈最后存进去的元素‘\[’与‘\]’判断，可以配对，将‘\[’退栈  
5.栈空，‘\{’是左括号，将‘\{’进栈  
6.‘\}’是右括号，取栈最后存进去的元素‘\{’’与‘\}’判断，可以配对，将‘\{’退栈  
7.循环结束，此时栈为空，故为true

> 输入: “(\[)\]”  
> 输出: false

输入的是"(\[)\]"，过程为：  
1.最开始栈中没有元素，‘（’是左括号，将‘（’进栈  
2.‘\[’是左括号，将‘\[’进栈  
3.‘）’是右括号，取栈最后存进去的元素‘\[’与‘）’配对，无法配对，false

> 输入: “\{\[\]\}”  
> 输出: true

输入的是"\{\[\]\}"，过程为：  
1.最开始栈中没有元素，‘\{’是左括号，将‘\{’进栈  
2.‘\[’是左括号，将‘\[’进栈  
3.‘\]’是右括号，取栈最后存进去的元素‘\[’与‘\]’配对，配对成功，将‘\[’出栈，此时栈中只有‘\{’  
4.‘\}’是右括号，取栈最后存进去的元素‘\{’与‘\}’配对，配对成功，将‘\{’出栈，此时栈为空  
5.循环结束，栈为空，true

# 代码 #

class Solution {
        public boolean isValid(String s) {
            //创建一个栈，用来存储字符
            Stack<Character> stack = new Stack<>();
            //将字符串转化为字符数组
            char[] chars = s.toCharArray();
             //遍历字符数组
            for (char aChar : chars) {
                 //如果栈为空，将当前元素进栈
                if (stack.size() == 0) {
                    stack.push(aChar);
                } else if (isSym(stack.peek(), aChar)) {
                    //如果栈不为空，且进栈为右括号，并且配对成功，则出栈一个元素
                    stack.pop();
                } else {
                    //如果栈不为空，且进栈为左括号，则进栈
                    stack.push(aChar);
                }
            }
            //判断最后数组是否为空
            return stack.size() == 0;
        }
        //判断进栈元素是否是右括号，且是否能配对成功
        private boolean isSym(char c1, char c2) {
            return (c1 == '(' && c2 == ')') || (c1 == '[' && c2 == ']') || (c1 == '{' && c2 == '}');
        }
    }

## 结果 ##

![在这里插入图片描述][2019090814445578.png]

[2019090814445578.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/2c452f94d93b4eaab54cd978cbd8b005.png