NC52 有效括号序列

- 日理万妓 2024-03-27 16:53 12阅读 0赞

> [牛客华为机试题库【题号 HJ开头】（重点看）][HJ]  
> [牛客在线编程算法篇【题号NC开头】][NC]  
> [剑指offer【题号 JZ开头】][offer_ JZ]  
> [力扣][Link 1]

### 1）[原题链接][Link 2] ###

### 2）已有题解 ###

### 3）代码 ###

package stack;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Arrays;
    import java.util.Deque;
    import java.util.LinkedList;
    import java.util.List;
    
    import static java.lang.System.in;
    
    /**
     * NC52 有效括号序列
     */
    public class NC52ValidParenthesisSequence {
        
        public static void main(String[] args) throws IOException {
        
            BufferedReader bf = new BufferedReader(new InputStreamReader(in));
            String str = bf.readLine();
            bf.close();
    
            boolean valid = isValid(str);
            System.out.println(valid);
        }
    
        private static boolean isValid(String s) {
        
            List<Character> left = Arrays.asList('(', '[', '{');
            List<Character> right = Arrays.asList(')', ']', '}');
            Deque<Character> stack = new LinkedList<>();
            char[] chars = s.toCharArray();
            for (char aChar : chars) {
        
                if (left.contains(aChar)) {
        
                    stack.push(aChar);
                } else if (right.contains(aChar)) {
        
                    if (stack.isEmpty()) {
        
                        // 不存在左括号直接右括号的话有问题
                        return false;
                    }
                    Character pop = stack.pop();
                    if (!isPair(pop, aChar)) {
        
                        // 存在乱序
                        return false;
                    }
                }
            }
    
            // 数量不匹配,还有左括号
            if (stack.size() > 0) {
        
                return false;
            }
            return true;
        }
    
        public static boolean isPair(char c1, char c2) {
        
            if ('(' == c1 && ')' == c2) {
        
                return true;
            }
            if ('[' == c1 && ']' == c2) {
        
                return true;
            }
            if ('{' == c1 && '}' == c2) {
        
                return true;
            }
            return false;
        }
    }

[HJ]: https://www.nowcoder.com/exam/oj/ta?tpId=37
[NC]: https://www.nowcoder.com/exam/oj
[offer_ JZ]: https://www.nowcoder.com/exam/oj/ta?page=1&tpId=13&type=13
[Link 1]: https://leetcode.cn/problemset/all/
[Link 2]: https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2?tpId=196&tqId=37083&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?page=1&pageSize=50&search=NC52&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=196&difficulty=undefined&judgeStatus=undefined&tags=&title=NC52