Abc 307 D - Mismatched Parentheses

问题描述

给定一个长度为 N 的字符串 S，由小写英文字母和字符 ( 和 ) 组成。

执行下列操作尽可能多的次后，打印出字符串 S。

选择并删除 S 中一个以 ( 开头，以 结尾) 且除第一个和最后一个字符外不包含 ( 或 ) 的连续子字符串。

可以证明，执行该操作尽可能多的次后，字符串 S 是唯一确定的，而不依赖于操作方式。

约束

1≤N≤2×10 5

N 为整数。

S 是一个长度为 N 的字符串，由小写英文字母和字符 ( 和 ) 组成。

输入

输入来自标准输入，格式如下：

N

S

输出

打印答案。

样例输入 1

8

a(b(d))c

样例输出 1

ac

以下是一个可能的过程，执行该过程后 S 将变为 ac。

删除 S 中第四到第六个字符组成的子字符串 (d)，使其成为 a(b)c。

删除 S 中第二到第四个字符组成的子字符串 (b)，使其成为 ac。

该操作无法再执行。

----------

一开始想到的stack来处理，但是对于多层的括号，就不知道要做多少个stack来处理了，这里面就用一个变量加stringbuilder来做，如果是左括号，那么cnt++,如果是右括号，而且cnt>0，说明左边有左括号，然后就while循环，删除最后一个字符，直到是左括号，同时把左括号删除，cnt--，这样依次判定就可，其实如果是这样的话，那么就知道其实用stack也是可以的，但是要增加一个变量记录左括号入栈的数量，同时遇到右括号的时候，需要出栈，同时更新cnt的数量即可，最后放到字符串中，还要翻转一下才行。