• 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
  • 相关阅读:
    Arrays.asList() 使用说明
    代码随想录算法训练营19期第60天
    期权里的资金变化
    【模式识别】贝叶斯决策模型理论总结
    es6 export和export default的区别
    【YOLOv8改进[CONV]】SPDConv助力YOLOv8目标检测效果 + 含全部代码和详细修改方式 + 手撕结构图
    【源码及课件分享】Java实战项目之新冠疫情统计系统
    C语言中strcpy()
    基于机器学习和OpenCV的激光雷达数据分割和分类
    万物皆可集成系列：低代码释放用友U8+深度价值（2）—数据拓展应用
  • 原文地址：https://blog.csdn.net/weixin_50340097/article/details/126643598