AT_past202004_j 文字列解析

[problemUrl]: https://atcoder.jp/contests/past202004-open/tasks/past202004_j 英小文字 `a` ~ `z` と `(` と `)` からなる文字列 $ S $ が与えられます。 ある文字列 $ a $ と $ b $ に対して $ a+b $ を $ a $ と $ b $ をこの順に結合した文字列とします。 また、ある文字列 $ a $ に対して $ rev(a) $ を $ a $ を反転させた文字列とします。 以下の操作をこれ以上操作が行えなくなるまで繰り返し行ったときの、最終的な文字列 $ S $ を出力してください。 - `(` や `)` を含まない文字列 $ a $ (空文字列でもよい) に対して `(` $ +a+ $ `)` のような部分文字列が $ S $ の中にあったときに、 その部分文字列を $ a+rev(a) $ に置き換える ただし、文字列 $ S $ で正しい括弧の対応が取れていること、すなわち最終的な文字列 $ S $ に `(` や `)` は含まれないことが保証されています。また、この条件下で最終的な文字列は一意に定まることが示せます。

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

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

### 注意 この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ S $ は長さ $ 1 $ 以上 $ 1000 $ 以下の、英小文字 `a` ~ `z` と `(` と `)` からなる文字列である。 - $ S $ は $ 1 $ 文字以上の英小文字を含む。 - 操作をこれ以上操作が行えなくなるまで繰り返し行ったときの、最終的な文字列 $ S $ の長さは $ 1000 $ 以下であり、これに`(` や `)` は含まれない。 ### Sample Explanation 1 `(ab)` を `ab` $ +rev( $ `ab` $ ) $ である `abba` に置き換えると、$ S $ は `abbac` になります。 これ以上操作を行うことはできないので、これを出力します。 ### Sample Explanation 2 括弧が存在しない可能性もあります。 ### Sample Explanation 3 括弧の中が空文字列である可能性もあります。