B2165 括号匹配

题目描述

给定只由 \(6\) 种括号字符组成的字符串：(, ), [, ], {, }。判断每个字符串是否为“合法括号序列”，合法则输出 YES，否则输出 NO。合法括号序列的定义： - 空串合法； - 若 A 合法，则 (A), [A], {A} 均合法； - 若 A 与 B 均合法，则 AB 合法。

输入格式

第一行一个整数 \(T\)，表示数据组数。接下来 \(T\) 行，每行一个只包含上述 \(6\) 种字符的字符串。

输出格式

对于每个字符串，输出一行： - 若其为合法括号序列，输出 YES； - 否则输出 NO。

输入输出样例 #1

输入 #1

1
()[]{}

输出 #1

YES

输入输出样例 #2

输入 #2

6
()
([)]
([]){}
((((
{[()()]}
}{

输出 #2

YES
NO
YES
NO
YES
NO

说明/提示

记单串长度记为 \(|S|\)。测试数据满足 \(1 \leq |S| \leq 10^6\)，\(1 \leq T \leq 2\times 10^5\)，同一输入文件内总长度 \(\sum |S| \leq 2\times 10^6\)，字符串只包含字符 ()[]{}。

Tip

b站讲解链接

📌 题目分析

给定数据：

T 组测试数据，包含 () [] {} 三种括号的字符串。
总长度最高达到 2 × 10^6。

要求判断每一组括号序列是否能完美闭合匹配。

👉 本质：

后遇到的左括号，必须先被闭合（后进先出）

👉 类型：

经典 数据结构：栈 (Stack) 的基础应用

🧠 解题思路

1️⃣ 为什么“栈”是完美解法？

括号匹配的核心规律是：最后出现的左括号，最先等来它的右括号。 这与栈的特性 “后进先出 (LIFO - Last In First Out)” 完美契合。 每当我们遇到一个右括号时，它必须和前面最近的且还没被匹配的左括号凑成一对。

2️⃣ 使用 STL stack 的核心逻辑

我们利用 C++ 标准模板库（STL）中的 <stack>： * 遇到左括号 (, [, {：直接压入栈中（push）。因为它们都在等待未来的右括号来拯救。 * 遇到右括号 ), ], }： 1. 先检查栈是否为空。如果栈空了，说明没有左括号能和它匹配，直接判定为不合法 (NO)。 2. 如果栈不空，取出栈顶元素（top），看看它俩是不是“天生一对”。 3. 如果是，匹配成功，将栈顶的左括号弹出（pop），继续看下一个字符。 4. 如果不是（比如遇到 ]，但栈顶是 (），直接判定为不合法 (NO)。

3️⃣ 最终的“清算”

当整个字符串遍历完后，我们还需要做最后一步检查： 栈必须是空的！ 如果栈里还有残留的左括号（说明左括号比右括号多），依然判定为不合法 (NO)。只有完全清空，才是合法的 (YES)。

4️⃣ 时间复杂度

遍历一次字符串，每个字符最多入栈一次、出栈一次。

单次判断复杂度：O(|S|)
总体时间复杂度：O(Σ|S|)

在 \(2 \times 10^6\) 的数据量下，整体时间完全控制在 \(O(N)\) 级别，非常高效。

---

💻 C++代码

#include <iostream>
#include <string>
#include <stack>

using namespace std;

// 独立封装一个检查函数，逻辑更清晰
bool isValid(const string& s) {
    stack<char> st; // 局部变量：每处理一个字符串自动初始化一个新栈

    for (char c : s) {
        // 1. 左括号无脑入栈
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } 
        // 2. 遇到右括号，进行消除匹配
        else {
            // 如果栈是空的，说明没有左括号等它，直接判定非法
            if (st.empty()) return false;

            char top = st.top(); // 获取栈顶元素

            // 检查栈顶的左括号与当前的右括号是否匹配
            if ((c == ')' && top == '(') ||
                (c == ']' && top == '[') ||
                (c == '}' && top == '{')) {
                st.pop(); // 匹配成功，消除一对
            } else {
                return false; // 类型不匹配（例如 [) ），判定非法
            }
        }
    }

    // 3. 遍历结束后，只有栈空了才算完美匹配
    return st.empty();
}

int main() {
    // 优化大规模数据的输入输出速度，极其关键！
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    if (cin >> t) {
        while (t--) {
            string s;
            cin >> s;
            if (isValid(s)) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }

    return 0;
}

---

⚠️ 易错点

❌ 1. 遇到右括号时忘记判空导致 RE (运行错误)

如果输入是 )，栈此时是空的，直接调用 st.top() 或者 st.pop() 会直接导致程序崩溃。 防坑：处理右括号的第一步，永远是 if (st.empty()) return false;。

❌ 2. 多组数据时使用了全局栈而忘记清空

很多初学者喜欢把 stack<char> st; 定义在 main 函数外面当全局变量。这会导致上一组测试数据的残留符号干扰下一组判断。 防坑：推荐像上方代码一样，把栈的定义放在处理单个字符串的函数内部，每次调用都是一个干净的新栈。

❌ 3. 输入输出超时 (TLE)

题目明确指出总长度 \(\sum |S| \le 2\times 10^6\)，且测试数据可能高达 \(2 \times 10^5\) 组。如果你使用了 endl 而不是 \n，极其容易因为刷新缓冲区导致超时。 防坑：一定要加上 ios::sync_with_stdio(false); cin.tie(nullptr);，并坚持使用 \n。

---

🚀 一句话总结

左括号进栈，右括号碰一碰；碰对了一起消失，碰错了或者落单了就是 NO！

---

🔥 补充

STL std::stack 与“手写栈”的区别：

虽然使用 <stack> 库非常方便且安全，但在极度追求速度的算法竞赛（如 ACM/ICPC）中，很多大佬喜欢用数组手写栈：

char st[2000005];
int top = 0;

// 入栈
st[++top] = c;

// 出栈
top--;

// 判空
if (top == 0)

为什么？ 因为 std::stack 底层默认是基于 std::deque（双端队列）实现的，存在动态内存分配的开销。而手写数组栈在内存上是完全连续的，省去了函数调用的开销，速度可以比 STL 栈快 2 倍以上！ 不过对于普通的洛谷刷题，只要不被卡常数，STL 绝对是提高代码可读性和编写速度的最佳伴侣。