括号的消除题目描述给定一个字符串SSS这个字符串只含圆括号与小写英文字母。其中一对匹配的圆括号所包围的内容是要被删除的文字。如果这个字符串里有一段连续的字符以(开始以)结束且中间不含其他括号只包含英文字母或者为空那么就删除这段字符包括括号本身。不断重复这个过程直到没有内容可以删除为止。请输出经过不断删除后所留字符串的长度。输入格式一行字符串SSS只包含(、)和小写英文字母。输出格式一个整数表示经过不断删除后所留字符串的长度。数据范围记∣S∣|S|∣S∣表示输入字符串的长度30%30\%30%的数据1≤∣S∣≤1,0001 \leq |S| \leq 1,0001≤∣S∣≤1,000100%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 万的数据规模。下面是我实现的代码已按原样保留并逐行添加了注释以便理解#includebits/stdc.husingnamespacestd;stackcharsk;// 用栈存储所有尚未被删除的字符string s;intcnt0;// 记录当前栈中未被匹配的左括号 ( 的个数intmain(){cins;// 读入原始字符串for(inti0;is.size();i){// 逐个字符处理if(s[i])){// 遇到右括号if(cnt0){// 当前有未匹配的左括号说明可以配对删除// 删除这一对括号及其内部内容弹出直到遇到左括号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]);// 字母直接入栈暂时保留}}coutsk.size();// 栈中剩余字符数即为最终字符串长度return0;}