上海计算机学会2026年月7月赛C++丙组T3 括号的消除
括号的消除
题目描述
给定一个字符串SSS，这个字符串只含圆括号与小写英文字母。
其中，一对匹配的圆括号所包围的内容，是要被删除的文字。
如果这个字符串里，有一段连续的字符以(开始，以)结束，且中间不含其他括号，只包含英文字母或者为空，那么就删除这段字符（包括括号本身）。
不断重复这个过程直到没有内容可以删除为止。
请输出，经过不断删除后，所留字符串的长度。
输入格式
一行字符串SSS，只包含(、)和小写英文字母。
输出格式
一个整数，表示经过不断删除后所留字符串的长度。
数据范围
记∣S∣|S|∣S∣表示输入字符串的长度：
- 30%30\%30%的数据，1≤∣S∣≤1,0001 \leq |S| \leq 1,0001≤∣S∣≤1,000
- 100%100\%100%的数据，1≤∣S∣≤500,0001 \leq |S| \leq 500,0001≤∣S∣≤500,000
样例
样例1
输入:
x(y(z))w输出:
2说明：只留下xw。过程：x(y(z))w→ 删(z)→x(y)w→ 删(y)→xw
样例2
输入:
)()(输出:
2说明：留下)(。过程：)()(→ 删()→)(
样例3
输入:
(a(b)输出:
2说明：剩(a。过程：(a(b)→ 删(b)→(a
题目来源：改编自 ABC307D
题解
拿到这道题，我首先注意到删除规则是“删除一对匹配的圆括号以及它们包围的内容”，而且要求括号内部不能有其他括号（即最内层括号对）。这其实就是一个经典的括号匹配问题，只不过匹配成功后要把匹配的括号及其内部内容都删掉，而不是仅仅标记或计数。
我考虑用栈来模拟这个过程，因为栈能很好地处理最近匹配的括号。同时，由于需要删除括号内部的所有字符，当遇到右括号时，如果它前面有未匹配的左括号，那么当前栈中从栈顶到那个左括号之间的所有字符（都是英文字母，因为内部不能有括号）就都属于这个括号对的内容，应该全部弹出并丢弃，然后弹出左括号自身。
为了区分哪些左括号是“未匹配”的，我维护了一个计数器cnt，它表示当前栈中未匹配的左括号数量。每当遇到左括号，cnt加 1，同时将左括号入栈；每当遇到右括号，如果cnt > 0，说明存在一个左括号可以与它匹配，那么我就执行删除操作：弹出栈顶直到遇到左括号（这些被弹出的字母就是括号内的内容），然后再弹出那个左括号，并将cnt减 1。如果cnt == 0，说明这个右括号没有匹配的左括号，它本身应该保留，所以直接入栈。对于普通小写字母，它们既不是括号，也无需特殊处理，直接入栈即可。
为什么这样是正确的？因为每次删除的都是当前最内层的括号对（由于栈的后进先出特性，遇到右括号时，栈顶如果存在左括号，它一定是最内层的左括号，中间所有元素都是字母）。即使存在嵌套，例如(a(b)c)，第一次遇到右括号匹配的是内层(b)，将其删除后，外层括号内部变成(ac)，之后遇到下一个右括号会删除外层括号，最终达到题目要求的不断重复删除的效果。
最终栈中剩余的就是所有未被删除的字符，栈的大小就是答案。整个算法时间复杂度 O(n)，空间 O(n)，完全满足 50 万的数据规模。
下面是我实现的代码，已按原样保留，并逐行添加了注释以便理解：
#include<bits/stdc++.h>usingnamespacestd;stack<char>sk;// 用栈存储所有尚未被删除的字符string s;intcnt=0;// 记录当前栈中未被匹配的左括号 '(' 的个数intmain(){cin>>s;// 读入原始字符串for(inti=0;i<s.size();i++){// 逐个字符处理if(s[i]==')'){// 遇到右括号if(cnt>0){// 当前有未匹配的左括号，说明可以配对删除// 删除这一对括号及其内部内容：弹出直到遇到左括号while(sk.top()!='('){sk.pop();// 弹出括号内的字母（它们将被丢弃）}sk.pop();// 弹出匹配的左括号自身cnt--;// 已匹配一个左括号，计数减一}else{// 没有左括号与之匹配，右括号作为普通字符保留sk.push(s[i]);}}elseif(s[i]=='('){// 遇到左括号cnt++;// 未匹配左括号数量加一sk.push(s[i]);// 左括号入栈}else{// 遇到小写英文字母sk.push(s[i]);// 字母直接入栈（暂时保留）}}cout<<sk.size();// 栈中剩余字符数即为最终字符串长度return0;}