括号匹配
->返回c/c++蓝桥杯经典编程题100道-目录
目录
括号匹配
一、题型解释
二、例题问题描述
三、C语言实现
解法1：栈匹配法（难度★）
解法2：计数器法（仅限单一括号类型，难度★☆）
四、C++实现
解法1：使用STL栈（难度★）
解法2：哈希表优化（难度★★）
五、总结对比表
六、特殊方法与内置函数补充
1. C语言中的动态栈
2. C++的 unordered_map
3. 递归解法（不推荐）
一、题型解释
括号匹配是验证字符串中的括号是否正确闭合的问题。常见题型：
-
基础匹配：验证字符串中的
()、[]、{}是否成对且顺序正确。 -
包含其他字符：字符串中混合其他字符（如字母、数字），需跳过非括号字符。
-
最长有效括号子串：找到字符串中最长的有效括号子串长度。
-
最小添加次数：计算使括号匹配所需最少添加的括号数量。
二、例题问题描述
例题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;
}代码逻辑：
-
栈初始化：数组
stack模拟栈，top表示栈顶索引。 -
遍历字符：
-
左括号：入栈，
top加1。 -
右括号：若栈为空直接失败；否则弹出栈顶元素检查是否匹配。
-
-
最终检查：遍历结束后栈必须为空，否则存在未闭合的左括号。
解法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。
-
中途检查：计数器不能为负（右括号比左括号多）。
-
最终检查：计数器归零。
-
局限性：无法处理混合括号类型（如
[)）。
四、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;
}代码逻辑：
-
哈希表存储映射：键为右括号，值为对应的左括号。
-
简化条件判断：遇到右括号时，直接从哈希表取对应的左括号进行比较。
五、总结对比表
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 栈匹配法 | 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道-目录
