经典括号匹配问题——你真的明白了吗？

忘是亡心i 2024-04-06 13:58 110阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：渴望力量的土狗
> 
> 博客主页：[渴望力量的土狗的博客主页][Link 1]
> 
> 专栏：[手把手带你刷牛客][Link 2]
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击免费注册和我一起刷题吧][Link 3]

**目录**

前言：

题目描述：

算法思想及解析：

完整代码实现：

--------------------

## 前言： ##

括号匹配问题是经典中的经典，是学习栈的经典例题，今天就再解剖一下这一经典例题，且看下文！

利用LeetCode的经典题目，详细揭开括号匹配问题的神秘面纱。

题目链接：[有效的括号][Link 4]

## 题目描述： ##

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。  
左括号必须以正确的顺序闭合。  
每个右括号都有一个对应的相同类型的左括号。

**示例 1:**

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

**示例 2:**

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

**示例 3:**

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

## 算法思想及解析： ##

![199849df397f431286d4737e6c9e86ec.png][]

注意这一段代码：![aaab942990b24dc7acf99b7b7ca736b8.png][]

括号一定是匹配的，要不然是会出错的。

还有别忘记再判断栈是否为空了

![d1ebb7b8f3f34f5d99cb100a56919761.png][]

## 完整代码实现： ##

class Solution {
        public boolean isValid(String s) {
    
                Stack<Character>stack=new Stack<>();
    
                for(int i=0;i<s.length();i++){
                    char ch=s.charAt(i);
                    if(ch=='('||ch=='['||ch=='{'){//左括号入栈
                        stack.push(ch);
                    }else{          //右括号匹配则出栈,不匹配就是false
    
                    if(!stack.empty()&&stack.peek().equals(stackOf(ch))){
    
                        stack.pop();
    
                    }else{
                        return false;
                    }
    
    
                    }
                    
                }
    
                if(stack.empty()){
                    return true;
                }else{
                    return false;
                }
        }
    
        public char stackOf(char ch){
           if(ch==')')return '(';
           if(ch==']')return '[';
           return '{';
           
        }
    }

代码调试无误：

![5617fc979d31436687ce4f644f1e6cf5.png][]

[ced485cbb11e458d81a746890b32cf3f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/d28e3e1904064ab0a9495d8d2a67999d.gif
[Link 1]: https://blog.csdn.net/m0_67995737?type=blog
[Link 2]: https://blog.csdn.net/m0_67995737/category_11980422.html
[Link 3]: https://www.nowcoder.com/link/pc_csdncpt_ylcxx_c
[Link 4]: https://leetcode.cn/problems/valid-parentheses/
[199849df397f431286d4737e6c9e86ec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/1f30ad9ebaba43a59024d59b0bbc2938.png
[aaab942990b24dc7acf99b7b7ca736b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/81ccb763ed2340dc9dfce5ecf66d2e69.png
[d1ebb7b8f3f34f5d99cb100a56919761.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/d6adf26ce71041b6b30cdaad6561981d.png
[5617fc979d31436687ce4f644f1e6cf5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/f3aa762d2d224e8db4f3bcc576b00699.png