題目來源：Valid Parentheses

問題：
給予一個字串並包含了括號 '[', ']', '(', ')' 和 '{', '}'，請驗證該字串中的括號是否合法配對。
也就是 "([])", "{()}", "[]" 為合法配對，但是 "(]", 或 "([)]" 就是不合法配對。

想法
有左邊的括號就一定要有右邊的括號，而左括號的出現順序剛好會與又括號的出現順序相反（不論大括號、小括號或中括號）！
也就是假設下面這個字串 ： { { [ (3+5) * 2 ] + [ (6-3)*(5+8)/(6+9+1)] } / 2 }
我們可以從中觀察到以下幾點：

1. 括號數量一定是偶數
2. 有左邊系列括號，就一定有右邊系列括號
3. 越慢出現的左邊括號，他的右邊括號就越早出現(順序相反)。

從已上三點可以察覺出，第三點最為重要，應為他包含了前面兩點。而他的特性就是左括號最先出現，則可以配對的右括號就會最後出現，所以我們可以利用 Stack 的特性來完成，因為 Stack 有先進後出的特性，完全可以符合『越慢出現的左邊括號，他的右邊括號就越早出現』。我們只要當左邊括號出現時，就把他 Push 進 Stack, 當右邊括號出現時，再從 Stack Pop 出一個括號除來比對是否為同一系列即可。

所以關於這一題我們只要

1. 如果有 左邊 系列的括號出現，就把 左括號 Push 進 Stack

2. 如果有 右邊 系列的括號出現，就從 Stack 中 Pop 出一個 左括號 並比較是否為同系列

3. 最後只要再判斷 stack 中還有沒有孤單的 左括號 存在，如果沒有就是配對成功，如果有，當然就是配對失敗囉！

   public boolean isValid(String s) {
   Stack stack = new Stack();

   for(int i=0; i<s.length(); i++ ) {
           // 如果是左邊括號
       if (s.charAt(i) == '[' || s.charAt(i) == '{' || s.charAt(i) == '(') {
           stack.push(s.charAt(i) );
           // 如果是右邊括號
       } else if (s.charAt(i) == ']' || s.charAt(i) == '}' || s.charAt(i) == ')')
           if (stack.size() <=0 )
               return false;
           else if ( s.charAt(i) == ']' ) {
               // 從 Stack Pop 出一個來檢查配對
               char pair = stack.pop();
               if (pair != '[') return false;
           } else if ( s.charAt(i) == '}' ) {
               // 從 Stack Pop 出一個來檢查配對
               char pair = stack.pop();
               if (pair != '{') return false;
           } else if ( s.charAt(i) == ')' ) {
               // 從 Stack Pop 出一個來檢查配對
               char pair = stack.pop();
               if (pair != '(') return false;
           }  
       }
   }
   // 檢查有沒有落單的括號
   if (stack.size() > 0)
       return false;
   return true;
   

   }

完成！這樣就可以達到題目要求了！不過，程式碼似乎有點醜，我們來整理一下吧！
首先可以把 s.charAt(i) == '[' || s.charAt(i) == '{' || s.charAt(i) == '(' 抽出來，增加可讀性

public boolean isLeftParentheses(Character c) {
    if ( c == '[' || c == '{' || c == '(' )
        return true;
}

再來就是在 else 裡面可以看到有三個 "// 從 Stack Pop 出一個來檢查配對"，這裡也可以整理成一個，畢竟是做同一件事情。

... (略)
else if (isRightParentheses(s.charAt(i)) ) {
    if (stack.size() <=0 )
        return false;
     // 從 Stack Pop 出一個來檢查配對
     Character pair = stack.pop();
     Character ch = getParenthesesPair(s.charAt(i));
     if ( pair != ch )
         return false;
}
...  (略)            

其中，getParenthesePair() 主要的目的就是取輸入括號的另一個配對字元。

private Character getParenthesesPair(Character c) {
    if ( c == ']' )
        return '[';
    else if ( c == '}' )
        return '{';
    else if ( c == ')' )
        return '(';
    else
        return ' ';
    }

整理完之後，我們的程式碼就變得很清楚了：

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<Character>();
    
    for(int i=0; i<s.length(); i++ ) {        
        if (isLeftParentheses( s.charAt(i) ) ) {
            stack.push(s.charAt(i) );
        } else if (isRightParentheses(s.charAt(i)) ) {            
            if (stack.size() <=0 ) 
                return false;
            Character pair = stack.pop();
            Character ch = getParenthesesPair(s.charAt(i));
            if ( pair != ch )
                return false;
        }
    }
    
    if (stack.size() > 0) //檢查有沒有落單的左括號
        return false;
    return true;
}

private boolean isLeftParentheses(Character c) {
    if ( c == '[' || c == '{' || c == '(')
        return true;
    return false;
}

private boolean isRightParentheses(Character c) {
    if ( c==']' || c=='}' || c==')' )
        return true;
    return false;
}

private Character getParenthesesPair(Character c) {
    if ( c == ']' )
        return '[';
    else if ( c == '}' )
        return '{';
    else if ( c == ')' )
        return '(';
    else
        return ' ';
}