/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
英小文字および (, ) からなる長さ N の文字列 S が与えられます。
以下の操作を可能な限り繰り返したあとの S を出力してください。
- S の連続部分文字列であって、最初の文字が
(かつ 最後の文字が)かつ 最初と最後以外に(も)も含まないものを自由に 1 つ選び削除する
なお、操作を可能な限り繰り返したあとの S は操作の手順によらず一意に定まることが証明できます。
制約
- 1 \leq N \leq 2 \times 10^5
- N は整数である
- S は英小文字および
(,)からなる長さ N の文字列である
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
答えを出力せよ。
入力例 1
8 a(b(d))c
出力例 1
ac
例えば、以下の手順により操作後の S が ac となります。
- S の 4 文字目から 6 文字目までからなる部分文字列
(d)を削除する。S はa(b)cとなる。 - S の 2 文字目から 4 文字目までからなる部分文字列
(b)を削除する。S はacとなる。 - これ以上操作を行うことはできない。
入力例 2
5 a(b)(
出力例 2
a(
入力例 3
2 ()
出力例 3
操作後の S は空文字列になる可能性があります。
入力例 4
6 )))(((
出力例 4
)))(((
Score : 400 points
Problem Statement
You are given a string S of length N consisting of lowercase English letters and the characters ( and ).
Print the string S after performing the following operation as many times as possible.
- Choose and delete a contiguous substring of S that starts with
(, ends with), and does not contain(or)other than the first and last characters.
It can be proved that the string S after performing the operation as many times as possible is uniquely determined without depending on how it is performed.
Constraints
- 1 \leq N \leq 2 \times 10^5
- N is an integer.
- S is a string of length N consisting of lowercase English letters and the characters
(and).
Input
The input is given from Standard Input in the following format:
N S
Output
Print the answer.
Sample Input 1
8 a(b(d))c
Sample Output 1
ac
Here is one possible procedure, after which S will be ac.
- Delete the substring
(d)formed by the fourth to sixth characters of S, making ita(b)c. - Delete the substring
(b)formed by the second to fourth characters of S, making itac. - The operation can no longer be performed.
Sample Input 2
5 a(b)(
Sample Output 2
a(
Sample Input 3
2 ()
Sample Output 3
The string S after the procedure may be empty.
Sample Input 4
6 )))(((
Sample Output 4
)))(((