如何判断括号的合法性

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;
}

• 其实这道题与前面做过的一道题很像，在回溯算法中，我们做过括号生成这个题目，其中对于合法括号的性质描述如下
  • 一个合法括号组合的左括号数量一定等于右括号数量
  • 对一个合法的括号字符串p，必然对于任何0<=i<len(p)都有子串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 '(';
}