P4833 括号成对数量（入门）

解题思路

第一步，理解"成对"是什么意思。 表达式中只有中括号 [ ]，而且必须成对出现、正确嵌套。就像小朋友手拉手站成圈，最里面的 [ ] 先拉上手，再一层一层往外配对。例如 [[ ]] 或者 [[ ][ ]] 都是正确的格式；而 [[ ]（多了一个左括号）、[ ]]（多了一个右括号）、[[[（三个左括号）都是不正确的格式。

第二步，用一个"计数"来模拟栈。 我们其实不需要真的把括号存下来，只需要记住"到现在为止，还有几个左括号没有配上对"。用变量 top 记录这个数。遇到左括号 [ 时，top 加1，表示多了一个没配对的左括号；遇到右括号 ] 时，先看看 top 是不是0：如果是0，说明根本没有左括号可以配，格式直接判错；否则 top 减1，表示一个左括号成功配上对，配对数 cnt 加1。

第三步，扫描完之后的判断。 有两种情况都说明格式不正确：一是中途遇到右括号时 top 已经为0（右括号多了）；二是扫描结束后 top 还大于0（说明有的左括号一直没配上对）。这两种情况都输出 NO。只有全程顺利、最后 top 恰好为0，才输出 YES，后面跟着配对数 cnt。

第四步，举两个例子感受一下。 输入 [[ ]]：先遇到两个 [，top 变成2；遇到第一个 ]，top 变1、cnt 变1；遇到第二个 ]，top 变0、cnt 变2。最后 top=0，格式正确，输出 YES 2。再比如输入 [[[：top 一路加到3，最后 top=3 大于0，说明有三个左括号没人配，输出 NO。括号数量不超过100，所以用数组或者干脆只计数都装得下。

参考代码

// 括号成对数量：用栈检测中括号是否成对匹配，正确输出YES和成对数
#include <iostream>
#include <cstring>
using namespace std;

int main() {
    char s[205];
    cin.getline(s, 205);
    int len = (int)strlen(s);
    int top = 0;   // 还未配对的左括号个数（栈深度）
    int cnt = 0;   // 成功匹配的括号对数
    bool ok = true;
    for (int i = 0; i < len; i++) {
        char c = s[i];
        if (c == '[') top++;   // 左括号入栈
        else if (c == ']') {
            if (top == 0) { ok = false; break; }  // 没有左括号可配，错误
            top--;         // 弹出配对的左括号
            cnt++;         // 成对数加1
        }
        // 其他字符忽略
    }
    if (!ok || top > 0) cout << "NO" << endl;  // 栈里还有左括号，错误
    else cout << "YES " << cnt << endl;
    return 0;
}

复杂度分析

括号的数量不超过100，程序从头到尾把每个字符看一遍，每个左括号或右括号都只处理一次，所以时间复杂度是 O(n)，其中 n 是括号的个数。空间上只需要几个变量来记录配对数量和栈深度，空间复杂度是 O(1)。