算法通关村——括号匹配问题的解析

落日映苍穹つ 2024-03-23 17:30 36阅读 0赞

## 括号匹配问题 ##

> 栈的典型题目还是非常明显的：括号匹配、表达式计算等几乎都少不了栈。

### 题目要求 ###

> 给定一个只包含'(',')','\{','\}','\[','\]' 的字符串s，判断字符串是否有效。有效字符串需满足：
> 
> 1. 左括号必须使用相同类型的右括号闭合
> 
> 2. 左括号必须以正确的顺序闭合

### 示例 ###

> \* 示例：  
> \* 输入：s = "()\[\]\{\}"  
> \* 输出：true

### 思路解析 ###

> 题目要点：判断两个符号是不是一组的
> 
> 方法一：
> 
> 使用哈希表将所有符号先存储，括号左半边做key，括号右半边做value，遍历字符串的时候，遇到左半边符号就入栈，遇到右半边符号就与栈顶的符号进行比较，不匹配就返回false。
> 
> 方法二：
> 
> 不使用哈希表，直接将要判断的字符串转成字符数组，遍历字符数组时，只关注左半边括号，一旦出现左半边括号，就将对应的右半边括号入栈。最后将栈的出栈元素（stack.pop()）和字符串中的字符进行匹配，如果没有相等的 或者 当栈的元素为空时（输入的字符串肯定是先出现左括号，如果先出现右括号，表示不合法；由此，一旦出现左括号，要想该字符串合法，必须出现和该左括号匹配的右括号，如果栈中的右半边括号为空，说明没有出现过左括号，或者说 先出现的是右括号，导致栈中没法加入左括号，最后栈中元素为空），说明就是非法的字符。

### 代码实现 ###

#### 方法一、使用hash表 ####

/**
         * 给定一个只包含'(',')','{','}','[',']' 的字符串s，判断字符串是否有效。有效字符串需满足：
         *  1. 左括号必须使用相同类型的右括号闭合
         *  2. 左括号必须以正确的顺序闭合
         *  示例：
         *  输入：s = "()[]{}"
         *  输出：true
         * @param s  只包含'(',')','{','}','[',']' 的字符串
         * @return 是否合法
         */
        public boolean isVaild(String s){
            if (s.length() <= 1){
                return false;
            }
            HashMap<Character, Character> map = new HashMap<>();
            map.put('(',')');
            map.put('{','}');
            map.put('[',']');
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
                char item = s.charAt(i);
                if (map.containsKey(item)){
                    stack.push(item);
                }else {
                    if (!stack.empty()){
                        Character left = stack.pop();
                        Character right = map.get(left);
                        if (item != right){
                            return false;
                        }
                    }else {
                        return false;
                    }
                }
            }
            return stack.empty();
        }

#### 方法二、只用栈 ####

public boolean isVaild1(String s){
            if ((s.length()<=1)) {
                return false;
            }
    
            Stack<Character> stack = new Stack<>();
            char[] chars = s.toCharArray();
            for (char aChar : chars) {
                if (aChar == '('){
                    stack.push(')');
                }else if (aChar == '{'){
                    stack.push('}');
                }else if (aChar == '['){
                    stack.push(']');
                }else if (stack.empty() || stack.pop() != aChar){
                    return false;
                }
            }
    
            return stack.empty();
        }

#### 测试方法 ####

public static void main(String[] args) {
            String s = "{()}";
            BracketMatching matching = new BracketMatching();
            boolean vaild = matching.isVaild(s);
            boolean vaild1 = matching.isVaild1(s);
            System.out.println(vaild?"该字符串合法":"该字符串不合法");
            System.out.println(vaild1?"该字符串合法":"该字符串不合法");
        }

####  ####