有效的括号

有效的括号

自己做毫无思路，试图使用递归+二分法解决，但是无从下手

参考答案思路：
利用栈的思想，把左边括号push入栈，在遇到右侧括号时，pop出栈顶元素。如果栈顶元素与右括号刚好构成一对，则判断下一个字符，否则返回false

我的理解：
由于只存在括号，不管以何种形式，如果能够匹配必然会出现(){}[]这三种子串。
以()为例，一旦循环到了")" ，如果能够匹配,栈顶元素必为"("。而将"(" pop出栈后，可以视为把()这一对括号从字符串s中移除了。

有人的答案就是这样的，巧妙利用了(){}[]这三种情况必然出现的条件，把成对的括号删除，然后不断循环知道字符串变为空串或者无子串可删

       if len(s)%2 != 0:
            return False
        while '()' in s or '[]' in s or '{}' in s:
            s = s.replace('[]','').replace('()','').replace('{}','')
        return True if s == '' else False #循环完毕，若空串说明全都匹配，不为空说明有不匹配的地方

正例：
{()}
[{}]()
反例：
)(
[(]
[{]}
很容易看到反例中是不可能出现成对的括号直接出现而中间不带任何其他字符的。
下面是我根据参考答案自己写的便于理解的代码

//下面的代码中可以去掉String.valueOf ，把.equals改为 == ，双引号改为单引号（好久没写java，忘记了单引号中的是char类型了，所以一开始写的时候全都转成了String进行比较，目测转成char类型应该可以节省一些内存占用）
public class bracketMatch {
    public boolean isValid(String s) {
        if (s == "") {
            return true;
        } else {    
            if (s.length() % 2 == 1) {  
                return false;//成对出现字符串长度必为偶数
            } else { 
                Stack<Character> stack = new Stack<Character>();
                for (int i = 0; i < s.length(); i++) {      
                    if (String.valueOf(s.charAt(i)).equals("(")|| String.valueOf(s.charAt(i)).equals("{")
                            || String.valueOf(s.charAt(i)).equals("[")) {
                        
                        stack.push(s.charAt(i));
                    } else {
                        char pop_char = stack.pop();
                        if(stack.isEmpty())//如果出现右半边括号，但是栈为空，必不匹配
                            return false;
                        System.out.println(pop_char);
                        if (String.valueOf(s.charAt(i)).equals(")")) {
                            if (String.valueOf(pop_char).equals("(") ) {
                                continue;
                            } else {
                                return false;
                            }
                        }
                        if (String.valueOf(s.charAt(i)).equals("]")  ) {
                            if (String.valueOf(pop_char).equals("[") ) {
                                continue;
                            } else {
                                return false;
                            }
                        }
                        if (String.valueOf(s.charAt(i)).equals("}")) {
                            if (String.valueOf(pop_char).equals("{")) {
                                continue;
                            } else {
                                return false;
                            }
                        }
                    }
                }
                if(stack.isEmpty())//循环结束，栈内无元素说明左侧括号全都找到匹配
                return true;
                else {//循环结束，栈内仍有元素 例："(("，根本不进入遇到右侧括号时的判断
                    return false;
                }
            }
        }
    }
}

当然也有更简单的写法，比如在遇到左括号 ( 时，直接push 右括号 ) 进入栈内，当循环遇到右括号时，pop栈顶元素比较栈顶元素和右括号是否相同，如下所示

public boolean isValid(String s) {
        if(s.isEmpty())
            return true;
        Stack<Character> stack=new Stack<Character>();
        for(char c:s.toCharArray()){
            if(c=='(')
                stack.push(')');
            else if(c=='{')
                stack.push('}');
            else if(c=='[')
                stack.push(']');
            else if(stack.empty()||c!=stack.pop())
        //empty对应 ："))"的情况
        //c!=stack.pop对应 括号不匹配
                return false;
        }
        if(stack.empty())
            return true;
        return false;
    }