c/c++蓝桥杯经典编程题100道（18）括号匹配

括号匹配

->返回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：栈匹配法（难度★）

通俗解释：

像叠盘子一样，遇到左括号“放入盘子”，遇到右括号时检查最上面的盘子是否匹配。

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define MAX_SIZE 10000

bool 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，中途不能为负，最终必须归零（仅适用于单一括号类型，如纯 ()）。

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("(()())")); // 输出 1
    printf("%d\n", isValidSingleType("())"));    // 输出 0
    return 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/0
    cout << isValid("{[()]}") << endl; // 输出 true
    cout << isValid("([)]") << endl;   // 输出 false
    return 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; // 输出 true
    return 0;
}

代码逻辑：

哈希表存储映射：键为右括号，值为对应的左括号。
简化条件判断：遇到右括号时，直接从哈希表取对应的左括号进行比较。

五、总结对比表

方法	时间复杂度	空间复杂度	优点	缺点
栈匹配法	O(n)	O(n)	支持所有括号类型	需要额外空间
计数器法	O(n)	O(1)	空间高效	仅支持单一括号类型
STL栈	O(n)	O(n)	代码简洁	依赖STL库
哈希表优化	O(n)	O(n)	代码可读性高	需理解哈希表