java实现括号匹配

桃扇骨 2024-03-17 11:29 58阅读 0赞

## 题目 ##

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

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

## 实例 ##

![在这里插入图片描述][6dbcba17389a494da0f1c0800944180c.png]  
原题OJ链接

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

## 解答（带测试） ##

//括号匹配
    public class Test {
        
        public static void main(String[] args) {
        
            String str1 = "()))";
            String str2 = "(((()))";
            String str3 = "[{()}]";
            String str4 = "}{()}]";
            System.out.println(isValid(str1));
            System.out.println(isValid(str2));
            System.out.println(isValid(str3));
            System.out.println(isValid(str4));
        }
        public static boolean isValid(String s) {
        
            Stack<Character> stack = new Stack<>();
            int  i = 0;
            for (i = 0; i < s.length(); i++) {
        
                char ret = s.charAt(i);
                if(ret == '(' || ret == '{' || ret == '['){
        
                    stack.push(ret);
                }
                else{
        
                    if(stack.isEmpty()){
        
                        return false;//证明第一个就是右括号，肯定不匹配
                    }
                    else{
        
                        char ret2 = stack.peek();
                        if(ret2 == '('&& ret == ')' || ret2 == '['&& ret == ']'|| ret2 == '{'&& ret == '}'){
        
                            stack.pop();
                        }
                        else{
        
                            return false;//不匹配
                        }
                    }
                }
            }
            if(!stack.isEmpty() || i !=s.length() ){
        
                return false;
            }
            return true;
        }
    }

结果  
![在这里插入图片描述][999a334234b646a6a48c9ad58acdfd4b.png]

[6dbcba17389a494da0f1c0800944180c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/f318bd88799a457b9234278124625abc.png
[999a334234b646a6a48c9ad58acdfd4b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/d1e6ce0423ea4e89af7a2616ac8eff2d.png