有效的括號(hào)

自己做毫無思路，試圖使用遞歸+二分法解決，但是無從下手

參考答案思路：
利用棧的思想，把左邊括號(hào)push入棧，在遇到右側(cè)括號(hào)時(shí)，pop出棧頂元素。如果棧頂元素與右括號(hào)剛好構(gòu)成一對(duì)，則判斷下一個(gè)字符，否則返回false

我的理解：
由于只存在括號(hào)，不管以何種形式，如果能夠匹配必然會(huì)出現(xiàn)(){}[]這三種子串。
以()為例，一旦循環(huán)到了")" ，如果能夠匹配,棧頂元素必為"("。而將"(" pop出棧后，可以視為把()這一對(duì)括號(hào)從字符串s中移除了。

有人的答案就是這樣的，巧妙利用了(){}[]這三種情況必然出現(xiàn)的條件，把成對(duì)的括號(hào)刪除，然后不斷循環(huán)知道字符串變?yōu)榭沾蛘邿o子串可刪

       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 #循環(huán)完畢，若空串說明全都匹配，不為空說明有不匹配的地方

正例：
{()}
[{}]()
反例：
)(
[(]
[{]}
很容易看到反例中是不可能出現(xiàn)成對(duì)的括號(hào)直接出現(xiàn)而中間不帶任何其他字符的。
下面是我根據(jù)參考答案自己寫的便于理解的代碼

//下面的代碼中可以去掉String.valueOf ，把.equals改為 == ，雙引號(hào)改為單引號(hào)（好久沒寫java，忘記了單引號(hào)中的是char類型了，所以一開始寫的時(shí)候全都轉(zhuǎn)成了String進(jìn)行比較，目測(cè)轉(zhuǎn)成char類型應(yīng)該可以節(jié)省一些內(nèi)存占用）
public class bracketMatch {
    public boolean isValid(String s) {
        if (s == "") {
            return true;
        } else {    
            if (s.length() % 2 == 1) {  
                return false;//成對(duì)出現(xiàn)字符串長(zhǎng)度必為偶數(shù)
            } 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())//如果出現(xiàn)右半邊括號(hào)，但是棧為空，必不匹配
                            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())//循環(huán)結(jié)束，棧內(nèi)無元素說明左側(cè)括號(hào)全都找到匹配
                return true;
                else {//循環(huán)結(jié)束，棧內(nèi)仍有元素 例："(("，根本不進(jìn)入遇到右側(cè)括號(hào)時(shí)的判斷
                    return false;
                }
            }
        }
    }
}

當(dāng)然也有更簡(jiǎn)單的寫法，比如在遇到左括號(hào) ( 時(shí)，直接push 右括號(hào) ) 進(jìn)入棧內(nèi)，當(dāng)循環(huán)遇到右括號(hào)時(shí)，pop棧頂元素比較棧頂元素和右括號(hào)是否相同，如下所示

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對(duì)應(yīng) ："))"的情況
        //c!=stack.pop對(duì)應(yīng) 括號(hào)不匹配
                return false;
        }
        if(stack.empty())
            return true;
        return false;
    }