题解-Atcoder-abc307d

本文章遵守知识共享协议 CC-BY-NC-SA，同步发表于洛谷题解区，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

题意简述

给你一个含有括号的小写字母串，删除里面的所有括号对和其中的元素，让你输出删除完成后的串。

实现思路

既然遇到括号匹配，那我们大胆打一个栈上去。

别急，先别动手，因为有这样一种情况：

))a(b((c)d)

结果应该是：

))a(b

我们发现:不是所有括号都会被消除，不匹配的括号要保留。

检测到右括号时，若栈中没有左括号，那么这个右括号就不可能消去，只有这种情况要将右括号入栈，否则就将所有字符出栈直到左括号。

所以我们需要记录左括号的数量，在入栈和出栈时更新。

代码如下：

#include<stdio.h>
#include<string.h>
#include<set>
#include<algorithm>

#define maxn 200007

char ch[maxn],st[maxn];

int top,lcnt,lc,rc,t,n;

int main(){
    scanf("%d%s",&n,ch);

    for(int i=0;i<n;i++){
        if(ch[i]==')'){
            if(lcnt){
                while(st[top-1]!='(')top--;
                top--;
                lcnt--;
            }
            else
                st[top++]=')';
        }
        else
            st[top++]=ch[i],
            lcnt += (ch[i]=='(');
    }

    for(int i=0;i<top;i++)
        putchar(st[i]);

    return 0;
}