作为教练，制作“有效的括号”这类题目的数据时，关键在于平衡合法序列与非法序列的比例。如果全是随机字符串，绝大多数都会在开头就判定为 false，无法测出选手的逻辑深度。

我们需要构造：深度嵌套的合法序列、只有最后一位不匹配的近合法序列、以及栈溢出边缘的极端序列。

以下是为你准备的自动化数据生成器（C++14 标准）。

一、 数据生成器代码 (C++14)

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
#include <random>
#include <ctime>

using namespace std;

// ================= 标准标程逻辑 (用于生成 .out) =================
string get_standard_output(string s) {
    if (s.length() % 2 != 0) return "false";
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else {
            if (st.empty()) return "false";
            char t = st.top();
            if ((c == ')' && t == '(') || (c == ']' && t == '[') || (c == '}' && t == '{')) st.pop();
            else return "false";
        }
    }
    return st.empty() ? "true" : "false";
}

// ================= 辅助生成函数 =================
mt19937 rng(time(0));
char left_b[] = {'(', '[', '{'};
char right_b[] = {')', ']', '}'};

// 构造一个绝对合法的嵌套括号序列 (迭代法)
string gen_valid(int n) {
    string s = "";
    stack<char> st;
    int current_len = 0;
    while (current_len < n || !st.empty()) {
        // 如果还没达到长度限制，随机选择左括号入栈或右括号出栈
        if (current_len < n && (st.empty() || rng() % 2 == 0)) {
            int type = rng() % 3;
            s += left_b[type];
            st.push(right_b[type]); // 存储期待的右括号
            current_len++;
        } else if (!st.empty()) {
            s += st.top();
            st.pop();
            current_len++;
        }
    }
    return s;
}

// ================= 主生成逻辑 =================
void make_test(int id, string s) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";
    
    ofstream fout(in_name);
    fout << s << endl;
    fout.close();
    
    ofstream fans(out_name);
    fans << get_standard_output(s) << endl;
    fans.close();
    
    cout << "Case " << id << " generated. Length: " << s.length() << " Result: " << get_standard_output(s) << endl;
}

int main() {
    // 1-3: 样例数据
    make_test(1, "()");
    make_test(2, "()[]{}");
    make_test(3, "(]");

    // 4: 边界 - 只有一个右括号
    make_test(4, "]");

    // 5: 边界 - 长度为奇数 (提前返回)
    make_test(5, "(((");

    // 6: 深度嵌套合法序列 (L=100)
    make_test(6, gen_valid(100));

    // 7: 只有最后一位不匹配 (L=100)
    string s7 = gen_valid(98);
    s7 = "(" + s7 + "]"; // 把本应闭合的 ) 改成 ]
    make_test(7, s7);

    // 8: 栈空后再出现右括号
    make_test(8, "()()]]");

    // 9: 极限规模 - 最大合法嵌套 (L=10000)
    make_test(9, gen_valid(10000));

    // 10: 极限规模 - 全左括号 (测栈空间和最终 empty 判断)
    string s10 = "";
    for(int i=0; i<10000; ++i) s10 += "{";
    make_test(10, s10);

    return 0;
}

二、 测试点设计思路（创建 OJ 必读）

这 10 组数据涵盖了选手最容易出错的所有场景：

三、 考场避坑与优化建议

1. 非递归生成： 在 gen_valid 函数中，我使用了迭代+模拟栈的方式生成括号。如果使用递归生成（如 s = "(" + gen(n-2) + ")"），在生成 $10^4$ 长度时可能会导致生成器本身爆栈。

2. 空间溢出： $10^4$ 长度的 std::stack 占用内存非常小（约几百 KB），但如果是在某些嵌入式环境或极严限制（1MB）下，建议选手使用 char 数组模拟栈。

3. 读入优化： 虽然 $10^4$ 并不大，但养成习惯：在读入长字符串时，使用 cin.tie(0) 或直接用 scanf("%s", buf) 往往能救命。

4. 字符匹配小技巧： 教给学生一个竞赛小技巧：如果你不想写那么多 if-else，可以定义一个 check(char a, char b) 函数，或者利用 switch 语句。在 C++ 中，甚至可以用一个简单的 bool 函数或者 map<char, char> 来存储配对关系。

你可以运行这个生成器，它会自动在当前文件夹生成 20 个文件，直接打包上传到你的 OJ 即可。加油，祝你的学生在 NOI 取得好成绩！

你好，同学。这道“有效的括号”是栈（Stack）这种数据结构最经典的应用之一。在 NOI/NOIP 竞赛中，它常作为更复杂算法（如表达式求值、中缀转后缀）的基础子模块出现。

下面我为你给出符合 C++14 标准 的标准题解代码。

一、 有效的括号 标准题解 (C++14)

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

using namespace std;

/**
 * 逻辑核心：
 * 1. 遇到左括号，说明需要一个对应的右括号，压入栈中。
 * 2. 遇到右括号，检查栈顶是否为匹配的左括号。
 * 3. 任何不匹配（类型不对、栈提前空、最后栈不空）都判定为 false。
 */

bool isValid(string s) {
    // 优化 1：如果字符串长度是奇数，由于括号必须成对出现，它一定无效
    if (s.length() % 2 != 0) return false;

    stack<char> st;

    for (char c : s) {
        // 如果是左括号，直接入栈
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } 
        else {
            // 关键点 1：如果是右括号，此时栈必须不能为空
            // 如果栈为空，说明右括号多出来了（例如 "())"）
            if (st.empty()) return false;

            char top = st.top();
            // 关键点 2：检查栈顶元素是否与当前右括号匹配
            if ((c == ')' && top == '(') || 
                (c == ']' && top == '[') || 
                (c == '}' && top == '{')) {
                st.pop(); // 匹配成功，弹出栈顶
            } else {
                // 类型不匹配（例如 "(]"）
                return false;
            }
        }
    }

    // 关键点 3：遍历结束后，栈必须为空
    // 如果不为空，说明左括号多出来了（例如 "(()"）
    return st.empty();
}

int main() {
    // NOI 竞赛 I/O 加速
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    if (!(cin >> s)) return 0;

    // 输出 true/false 字符串
    if (isValid(s)) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }

    return 0;
}

二、 复杂度分析思考过程

1. 时间复杂度分析

• 扫描过程：程序只对字符串进行了一次从左到右的遍历（$O(n)$）。
• 栈操作：std::stack 的 push 和 pop 操作都是常数级别的，即 $O(1)$。
• 结论：总时间复杂度为 $O(n)$。对于 $n=10^4$ 的数据，运算量大约在 $10^4$ 级别，远远低于 1.0s 的限制。

2. 空间复杂度分析

• 存储空间：在最坏的情况下（比如输入全部是左括号 ((((((），我们需要把所有字符都压入栈中。
• 结论：空间复杂度为 $O(n)$。

三、 考场易错点与防坑指南

1. 忽略“先入栈后检查”的顺序： 有些同学会尝试先判断右括号再入栈，这会导致逻辑混乱。记住：左括号是“待解的谜题”，右括号是“谜底”。谜底必须去解开最近的一个谜题。

2. 栈空检查 (Stack Underflow)： 这是最高频的错点。在调用 st.top() 或 st.pop() 之前，必须先判断 st.empty()。如果不检查，当遇到输入如 ")" 时，程序会直接因越界访问而崩溃（Runtime Error）。

3. 最后栈不为空的情况： 输入 "(("。扫描完后，没有任何报错，但这不是有效的序列。必须在函数最后检查 st.empty() 是否为真。

四、 时间复杂度优化建议

虽然 $O(n)$ 已经是渐进意义上的最优，但在 NOI 考场上，你可以通过以下“黑科技”来压低常数，提升排名：

1. 数组模拟栈 (Static Array Stack)： std::stack 虽然方便，但其底层默认使用 std::deque，涉及较多内存分配。你可以手动用数组模拟：

   char st[10005];
   int top = 0;
   // 入栈：st[++top] = c;
   // 出栈：top--;
   // 查看：st[top];
   

   数组模拟栈的常数通常比 STL 容器小 3-5 倍。

2. ASCII 码技巧： 注意到 ( 和 ) 的 ASCII 码分别是 40 和 41，[ 和 ] 是 91 和 93，{ 和 } 是 123 和 125。 虽然它们的差值不完全统一，但你可以发现右括号和左括号的差值都在 1 或 2。通过 switch-case 或数组查找表（Lookup Table）来匹配，比一堆 if-else 判断要快。

3. 预判长度： 代码开头的 s.length() % 2 != 0 判定是一个非常好的“剪枝”操作，能瞬间排除一半的不合法情况。

教练寄语：这道题不仅是考栈，更是考你对逻辑边界条件的处理能力。在考场上，写完代码后，一定要用 (、)、(()、()) 这四个最简单的 case 走一遍脑内调试。加油！