提示: 欢迎访问OurACM平台。
Problem 1706 括号表达式

Accept: 421    Submit: 1202
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

仅由括号()组成的表达式称之为括号表达式。
如果括号表达式中的括号能够配对,我们称该括号表达式为对称括号表达式。
在括号表达式中,去除对称括号表达式,我们称剩余的括号表达式为非对称括号表达式。
在非称括号表达式的两端添加最少的括号使得该表达式成为一个对称表达式,我们称之为最小对称括号表达式。
对于括号表达式“)()((()”,“()()”为其对称括号表达式,“)((”为其非对称括号表达式,“()(())”为其最小对称括号表达式。
给定一个括号表达式,你的任务就是输出该表达式的非对称括号表达式和最小对称括号表达式。

Input

每组输入数据的第一行为一个字符串S,字符串S仅由‘(’和‘)’组成,字符串非空且长度小于10000。

Output

对于每组数据,如果字符串S是对称括号表达式,只需要输出原字符串;否则输出两行,第一行为该表达式的非对称括号表达式,第二行为该表达式的最小对称括号表达式。

Sample Input

))((() ()()

Sample Output

))(( (())(()) ()()

Source

福州大学第六届程序设计竞赛

Submit  Back  Status  Discuss