分数: 400 点
问题陈述
给你一个字符串 S 长度 N 组成 ( 和 )。你的任务是插入一些 ( 和 ) 进入 S 获得 正确的括号顺序.
这里,正确的括号序列定义如下:
()是正确的括号序列。- If X 是正确的括号序列,串联
(, X 和)这个顺序也是正确的括号顺序。 - If X 和 Y 是正确的括号序列,串联 X 和 Y 这个顺序也是正确的括号顺序。
- 每个正确的括号序列都可以从上述规则中推导出来。
找出可获得的最短正确括号序列。如果存在多个这样的序列,请找到字典顺序最小的一个。
约束
- 的长度 S is N.
- 1 ≤ N ≤ 100
- S 包括
(和).
输入
输入由标准输入按以下格式给出:
N S
输出
打印最短的正确括号序列中按字典顺序排列的最小字符串,该序列可以通过插入一定数量的 ( 和 ) 进入 S.
示例输入 1
3 ())
示例输出 1
(())
示例输入 2
6 )))())
示例输出 2
(((()))())
示例输入 3
8 ))))((((
示例输出 3
(((())))(((())))