J - Parse Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

英小文字 a ~ z と ( と ) からなる文字列 S が与えられます。 ある文字列 a と b に対して a+b を a と b をこの順に結合した文字列とします。 また、ある文字列 a に対して rev(a) を a を反転させた文字列とします。 以下の操作をこれ以上操作が行えなくなるまで繰り返し行ったときの、最終的な文字列 S を出力してください。

  • ( や ) を含まない文字列 a (空文字列でもよい) に対して ( +a+ ) のような部分文字列が S の中にあったときに、 その部分文字列を a+rev(a) に置き換える

ただし、文字列 S で正しい括弧の対応が取れていること、すなわち最終的な文字列 S に ( や ) は含まれないことが保証されています。また、この条件下で最終的な文字列は一意に定まることが示せます。

制約

  • S は長さ 1 以上 1000 以下の、英小文字 a ~ z と ( と ) からなる文字列である。
  • S は 1 文字以上の英小文字を含む。
  • 操作をこれ以上操作が行えなくなるまで繰り返し行ったときの、最終的な文字列 S の長さは 1000 以下であり、これに( や ) は含まれない。

入力

入力は以下の形式で標準入力から与えられる。

S

出力

操作をこれ以上操作が行えなくなるまで繰り返し行ったときの最終的な文字列 S を出力せよ。

入力例 1

(ab)c

出力例 1

abbac

(ab) を ab +rev( ab ) である abba に置き換えると、S は abbac になります。 これ以上操作を行うことはできないので、これを出力します。

入力例 2

past

出力例 2

past

括弧が存在しない可能性もあります。

入力例 3

(d(abc)e)()

出力例 3

dabccbaeeabccbad

括弧の中が空文字列である可能性もあります。

Score : 6 points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a string S consisting of lowercase English letters a through z, (, and ). For strings a and b, let a+b be the concatenation of a and b in this order. Also, for a string a, let rev(a) be the reversal of a. Print the string S after repeating the following operation until it cannot be applied.

  • If S has a substring of the form ( + a + ) where a is a string that does not contain (s or )s, replace that substring with a+rev(a).

Here, it is guaranteed that parentheses in S are balanced, that is, the final string will not contain (s or )s. Also, under this condition, it can be shown that the final string is uniquely determined.

Constraints

  • S is a string of length between 1 and 1000 (inclusive) consisting of lowercase English letters a through z, (, and ).
  • S contains one or more lowercase English letters.
  • The string S after repeating the operation until it cannot be applied has a length of at most 1000 and does not contain (s or )s.

Input

Input is given from Standard Input in the following format:

S

Output

Print the string S after repeating the following operation until it cannot be applied.

Sample Input 1

(ab)c

Sample Output 1

abbac

After replacing (ab) with ab +rev( ab ), that is, abba, S is abbac. We can do no more operations, so we should print this string.

Sample Input 2

past

Sample Output 2

past

The input may contain no parentheses.

Sample Input 3

(d(abc)e)()

Sample Output 3

dabccbaeeabccbad

There can be an empty string between parentheses.