括號匹配

->返回c/c++藍橋杯經典編程題100道-目錄

---

目錄

括號匹配

一、題型解釋

二、例題問題描述

三、C語言實現

解法1：棧匹配法（難度★）

解法2：計數器法（僅限單一括號類型，難度★☆）

四、C++實現

解法1：使用STL棧（難度★）

解法2：哈希表優化（難度★★）

五、總結對比表

六、特殊方法與內置函數補充

1. C語言中的動態棧

2. C++的?unordered_map

3. 遞歸解法（不推薦）

---

一、題型解釋

括號匹配是驗證字符串中的括號是否正確閉合的問題。常見題型：

1. 基礎匹配：驗證字符串中的?()、[]、{}?是否成對且順序正確。

2. 包含其他字符：字符串中混合其他字符（如字母、數字），需跳過非括號字符。

3. 最長有效括號子串：找到字符串中最長的有效括號子串長度。

4. 最小添加次數：計算使括號匹配所需最少添加的括號數量。

---

二、例題問題描述

例題1：輸入?"()[]{}"，輸出?true（所有括號正確匹配）。
例題2：輸入?"{[()]}"，輸出?true（嵌套括號正確匹配）。
例題3：輸入?"(]"，輸出?false（括號類型不匹配）。
例題4：輸入?"()(()"，輸出最長有效子串長度?2。

---

三、C語言實現

解法1：棧匹配法（難度★）

通俗解釋：

• 像疊盤子一樣，遇到左括號“放入盤子”，遇到右括號時檢查最上面的盤子是否匹配。

c

#include <stdio.h>
#include <stdbool.h>
#include <string.h>#define MAX_SIZE 10000bool isValid(char *s) {char stack[MAX_SIZE]; // 用數組模擬棧int top = -1;         // 棧頂指針for (int i = 0; s[i] != '\0'; i++) {char c = s[i];if (c == '(' || c == '[' || c == '{') { // 左括號入棧stack[++top] = c;} else { // 右括號檢查匹配if (top == -1) return false; // 棧為空，無法匹配char topChar = stack[top--];if ((c == ')' && topChar != '(') || (c == ']' && topChar != '[') || (c == '}' && topChar != '{')) {return false;}}}return top == -1; // 棧必須為空才完全匹配
}int main() {printf("%d\n", isValid("()[]{}")); // 輸出 1（true）printf("%d\n", isValid("([)]"));    // 輸出 0（false）return 0;
}

代碼邏輯：

1. 棧初始化：數組?stack?模擬棧，top?表示棧頂索引。

2. 遍歷字符：

   • 左括號：入棧，top?加1。

   • 右括號：若棧為空直接失敗；否則彈出棧頂元素檢查是否匹配。

3. 最終檢查：遍歷結束后棧必須為空，否則存在未閉合的左括號。

---

解法2：計數器法（僅限單一括號類型，難度★☆）

通俗解釋：

• 統計左右括號數量，左括號加1，右括號減1，中途不能為負，最終必須歸零（僅適用于單一括號類型，如純?()）。

c

bool isValidSingleType(char *s) {int balance = 0;for (int i = 0; s[i] != '\0'; i++) {if (s[i] == '(') balance++;else if (s[i] == ')') balance--;if (balance < 0) return false; // 中途右括號過多}return balance == 0;
}int main() {printf("%d\n", isValidSingleType("(()())")); // 輸出 1printf("%d\n", isValidSingleType("())"));    // 輸出 0return 0;
}

代碼邏輯：

1. 平衡計數器：遇到左括號加1，右括號減1。

2. 中途檢查：計數器不能為負（右括號比左括號多）。

3. 最終檢查：計數器歸零。

4. 局限性：無法處理混合括號類型（如?[)）。

---

四、C++實現

解法1：使用STL棧（難度★）

通俗解釋：

• 使用C++標準庫的?stack?容器，簡化棧操作。

cpp

#include <iostream>
#include <stack>
using namespace std;bool isValid(string s) {stack<char> st;for (char c : s) {if (c == '(' || c == '[' || c == '{') { // 左括號入棧st.push(c);} else {if (st.empty()) return false; // 棧為空，無法匹配char topChar = st.top();st.pop();if ((c == ')' && topChar != '(') || (c == ']' && topChar != '[') || (c == '}' && topChar != '{')) {return false;}}}return st.empty(); // 棧必須為空
}int main() {cout << boolalpha; // 輸出true/false而非1/0cout << isValid("{[()]}") << endl; // 輸出 truecout << isValid("([)]") << endl;   // 輸出 falsereturn 0;
}

代碼邏輯：

• 與C語言棧方法邏輯相同，但使用?stack<char>?簡化棧操作。

---

解法2：哈希表優化（難度★★）

通俗解釋：

• 使用哈希表存儲括號對，簡化條件判斷。

cpp

#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;bool isValidHash(string s) {stack<char> st;unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};for (char c : s) {if (pairs.find(c) == pairs.end()) { // 左括號入棧st.push(c);} else { // 右括號檢查匹配if (st.empty() || st.top() != pairs[c]) return false;st.pop();}}return st.empty();
}int main() {cout << isValidHash("()[]{}") << endl; // 輸出 truereturn 0;
}

代碼邏輯：

1. 哈希表存儲映射：鍵為右括號，值為對應的左括號。

2. 簡化條件判斷：遇到右括號時，直接從哈希表取對應的左括號進行比較。

---

五、總結對比表

方法	時間復雜度	空間復雜度	優點	缺點
棧匹配法	O(n)	O(n)	支持所有括號類型	需要額外空間
計數器法	O(n)	O(1)	空間高效	僅支持單一括號類型
STL棧	O(n)	O(n)	代碼簡潔	依賴STL庫
哈希表優化	O(n)	O(n)	代碼可讀性高	需理解哈希表

---

六、特殊方法與內置函數補充

1. C語言中的動態棧

• 實現方式：使用動態數組 (malloc?和?realloc) 實現棧，避免固定大小限制。

2. C++的?unordered_map

• 作用：快速查找鍵值對，用于括號映射關系。

3. 遞歸解法（不推薦）

• 局限性：遞歸深度與括號嵌套層數相關，可能導致棧溢出。

->返回c/c++藍橋杯經典編程題100道-目錄