• 5.9如何判断括号的合法性

    5.9 如何判断括号的合法性

    对括号的合法性判断是一个常见而且实用的问题，而且我们的代码可能会包括三种括号[]{}()，判断起来会具有一些难度

    给你输入一个字符串，其中包含[](){}六种括号，请判断这个字符串组成的括号是否合法

    对于这种全局难的问题，可以采用一种局部分析到全局的办法进行分析

    5.9.1 仅处理一种括号的情形

    字符串中只有圆括号，如果想让括号字符串合法，那么要做的是:让每一个右括号)找到一个左括号(和它匹配

    bool isVaild(string str){
    //待匹配的左括号数量
    int left = 0;
    for(char c:str){
        if(c == "("){
            left++;
        }else{
            //遇到右括号
            left--;
        }
        if(left <0){
            return false;
        }
    }
    return left == 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 其实这道题与前面做过的一道题很像，在回溯算法中，我们做过括号生成这个题目，其中对于合法括号的性质描述如下
      • 一个合法括号组合的左括号数量一定等于右括号数量
      • 对一个合法的括号字符串p，必然对于任何0<=i都有子串p[0...i]中左括号的数量都大于右括号的数量

    那么通过以上的启发，能否通过多定义几个left1、left2、left3来对括号进行计数从而解决问题呢?这显然是不行的，例如说一个样例([)]，这个样例中[]类的左括号数量等于右括号的数量，但是因为嵌套关系的限制，这是不正确的

    5.9.2 处理多种括号

    栈是一种先进后出的数据结构，在处理括号问题的时候尤其有用

    我们这道题就用一个名为left的栈来代替之前思路中的left变量，遇到左括号就入栈，遇到右括号就去栈中寻找最近的左括号，看是否匹配，这是处理多种括号的一种思路

        public boolean isValid(String s){
        Stack<Character> stack = new Stack<>();
        for(int i = 0;i<s.length();i++){
            char c = s.charAt(i);
            if(c == '{' || c == '(' || c == '['){
                //左括号直接入栈
                stack.push(c);
            }else{
                if(!stack.isEmpty() && leftOf(c) == stack.peek()){
                    stack.pop();
                }else{
                    return false;
                }
            }

        }
        return stack.isEmpty();
    }

    private char leftOf(char c){
        if(c == '}'){
            return '{';
        }
        if(c == ']'){
            return '[';
        }
        return '(';
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
  • 相关阅读:
    mysql中server_id的作用
    nginx基本配置参数
    P2918 [USACO08NOV] Buying Hay S(不一样的完全背包)
    AI办公自动化：批量根据Excel表格内容制作Word文档
    国内程序员真的不如国外国外程序员？到底差在哪里？
    25.cuBLAS开发指南中文版--cuBLAS中的Level-2函数symv()
    Xilinx FPGA 程序固化重新上电程序不运行的问题
    Zstack一面面经
    Ts中的Pick，Omit，Extract和Exclude区别
    苹果Meta都在冲的Pancake技术，中国VR团队YVR竟抢先交出产品答卷
  • 原文地址：https://blog.csdn.net/weixin_50340097/article/details/126643598