摘要訊息 : 使用堆疊來解決括號匹配問題和開關盒佈線問題.
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).
自創文章, 原著 : Jonny. 如若閣下需要轉發, 在已經授權的情況下請註明本文出處 :