摘要訊息 : 使用堆疊來解決括號匹配問題和開關盒佈線問題.

0. 前言

在資料結構中, 線型的結構使用得比較多的是向量. 除了向量之外, 用得最多的也許就是堆疊和佇列. 今天來說一下堆疊的兩個應用.

本文在 2022 年 5 月 2 日進行一次更新和修正. 修正之後本文已經歸檔, 不再享受更新.

1. 括號匹配

在 C++ 中, 有好幾種括號 : <>, {}, [], (), '', "". 編碼器在編碼的時候必定要進行語法的檢查, 那麼檢查括號是否相匹配非常重要. 那麼任意給定一段程式碼, 應該如何進行檢查呢?

斷言 1. 給定任意一種括號, 其右括號若可以和某一個左括號相匹配, 那麼所有和其種類相同的左括號中, 那個能夠匹配的左括號距離右括號的距離最近.

考慮函式宣告 :

template <typename T>
void f(int &(arr)[10], char = '\0', typename T::type<char> = "");

這其中有十四個括號需要進行匹配, 其中正確的配對是 1 - 2, 3 - 14, 4 - 5, 6 - 7, 8 - 9, 10 - 11, 12 - 13. 從左至右, 我們發現, 最先被發現的左括號直到最後遇到相同類別的右括號時才會被匹配, 這個和堆疊的性質有一些類似, 因此我們使用堆疊.

任給一段程式碼, 當遇到左括號的時候, 就將其放入堆疊; 當遇到右括號的時候, 若存在下列情況 :

  • 堆疊為空, 說明沒有左括號和這個右括號匹配;
  • 堆疊頂部的左括號和它不配對,

那麼就說明出現了括號不匹配的問題. 如果堆疊頂部的左括號剛好和右括號匹配, 那麼從堆疊中移除這個左括號. 還有一種情況需要注意, 就是當程式終結, 但是堆疊中還存在左括號. 這就說明沒有足夠的右括號和堆疊中的左括號匹配, 這也會導致括號不匹配的問題. 將這些描述實作為 C++ 程式碼就是 :

template <typename Stack, typename String>
bool bracket_match(const String &string) {
    Stack stack {};
    for(auto c : string) {
        switch(c) {
            case '(':
            case '[':
            case '<':
            case '\'':
            case '"':
            case '{':
                stack.push(c);
                break;
            case ')':
                if(stack.empty() or stack.top() not_eq '(') {
                    return false;
                }
                stack.pop();
                break;
            case ']':
                if(stack.empty() or stack.top() not_eq '[') {
                    return false;
                }
                stack.pop();
                break;
            case '>':
                if(stack.empty() or stack.top() not_eq '<') {
                    return false;
                }
                stack.pop();
                break;
            case '\'':
                if(stack.empty() or stack.top() not_eq '\'') {
                    return false;
                }
                stack.pop();
                break;
            case '"':
                if(stack.empty() or stack.top() not_eq '"') {
                    return false;
                }
                stack.pop();
                break;
            case '}':
                if(stack.empty() or stack.top() not_eq '{') {
                    return false;
                }
                stack.pop();
                break;
            default:
                break;
        }
    }
    return stack.empty();
}

上面程式碼的行為並不總是正確, 因為 <> 還有比較的含義. 因此對於 <> 還需要在符號表中檢查左右兩側的是關鍵字、型別還是表達式.

函式 bracket_matching 的實體特徵為函式參數的 string 的大小, 不妨記 n. 函式 bracket_matching 的空間複雜度為 O(n), 這是因為我們需要至多 n 個額外空間來儲存每一個括號. 最壞的情況下, n 個括號全部都是左括號. 函式 bracket_matching 在完全匹配的情況下, 時間複雜度為 O(n), 因為每一個括號我們都需要檢查; 如果中間我們檢查出某一個括號不匹配, 那麼接下來就不再檢查, 此時可能只檢查了 O(n) 個括號. 這個情況下的時間複雜度仍然為 O(n). 如果一開始就是右括號, 那麼此時的時間複雜度是最優的, 為 O(1).

2. 開關盒佈線

給定任意矩形, 在矩形的邊上存在若干個管腳 :

任意兩個管腳之間通過佈設一條金屬線來相連接, 這條金屬線稱為電線. 它被限定在了矩形區域之內, 即電線不可以穿過矩形的邊來到矩形之外的區域 :

另外, 如果兩條電線交叉, 那麼就會出現短路的情況 :

因此, 我們不允許實際佈線的過程中出現電線交叉的情況. 每一對要連結的管腳稱為網組. 對於任意給定的矩形, 上面隨即分佈著管腳, 我們需要確定這些給定的網組是否能夠連接並且不發生短路的情況. 這樣的問題稱為開關盒佈線問題.

我們注意到, 當一個網組相連接的時候, 連線必定會將矩形分成兩個區域. 若出現一個網組跨越了兩個區域, 就可以判定其不可佈線. 因此, 我們可以根據連線不可跨區域原則, 對網組是否可以在開關盒上面佈線進行判斷.

為了實現這一策略, 可以從任意管腳開始, 按順時針或著逆時針沿著開關盒的邊界進行尋訪. 為了方便表述, 我們按照某一順序從第一個管腳開始進行編號 : a_{1}, a_{2}, ..., a_{n}. 若 a_{1}a_{i} (i = 1, 2, ..., n) 相連接, 則將 a_{1} 放入堆疊. 首先處理 a_{1}a_{i} 之間所構成區域中的管腳連線. 若 a_{1} 不和 a_{2} 相連接, 則將 a_{2} 也放入堆疊, ... 以此類推. 當 a_{j} 遇到 a_{k} (i, j = 1, 2, ..., n) 相連接的時候, 那麼從堆疊頂部移除 a_{j}. 不斷重複上述步驟, 當所有管腳都尋訪完畢的時候, 堆疊中如果不存在任何管腳, 那麼這一組網組時可以在開關盒上進行佈線的; 否則, 就不可以在開關盒上面佈線, 這是由堆疊的性質決定的. 由於堆疊只能訪問到其頂部元素, 因此當出現不可佈線的情況的時候, 即使已經遇到了 a_{i}a_{j} (i, j = 1, 2, ..., n) 相連接, 但是 a_{i} 並不在堆疊頂部, 頂部元素也無法和 a_{j} 相連接. 因此, a_{j} 會被放入頂部, 從而導致堆疊中 a_{j} 之前的管腳都無法完成佈線.

斷言 2. 在開關盒佈線問題中, 若一組網組時可佈線的, 則在非最小區域內必定存在一個網組, 其要連接的兩個管腳對應的編號是相鄰的.

template <typename Stack, template <typename, typename> class Pair, size_t n>
bool check_wiring(const Pair<int, int> (&list)[n]) {
    Stack s {};
    for(auto c : list) {
        if(s.empty()) {
            s.push(c.first);
            continue;
        }
        if(s.top() == c.second) {
            s.pop();
        }else {
            s.push(c.first);
        }
    }
    return s.empty();
}

可能對於第二個樣板參數, 你有一些陌生. 這個樣板參數表示 Pair 是接受兩個參數的類別樣板. 對於 list, 從頭到尾也就是我們剛才的管腳排列 : a_{1}, a_{2}, ..., a_{n}.

和函式 bracket_matching 一樣, 函式 check_wiring 的實體特徵為 n, 也就是 list 陣列的元素個數. 因此同樣需要至多 n 個額外空間來儲存, 其空間複雜度為 O(n). 不論什麼情況, 函式 check_wiring 總會把 list 中所有的管腳都尋訪一邊, 因此時間複雜度為 O(n).