iT邦幫忙

DAY 28
0

連續30天,挑戰演算法系列 第 28

[Day28] 30 天挑戰演算法 - 驗證括號

題目來源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 ' ';
}

上一篇
[Day27] 30 天挑戰演算法 - 最後一個單字長度
下一篇
[Day29] 30 天挑戰演算法 - 合併兩個已排序的 List
系列文
連續30天,挑戰演算法30

尚未有邦友留言

立即登入留言