UVA1626 Brackets sequence
题目描述
我们将正规括号序列定义如下：
1. 空序列是正规括号序列。
2. 如果 $\text S$ 是一个正规括号序列，那么 $\text{(S)}$ 和 $\text{[S]}$ 都是正规括号序列。
3. 如果 $\text A$ 和 $\text B$ 都是正规括号序列，那么 $\text{AB}$ 是一个正规括号序列。
例如，下面这些序列都是正规括号序列：
$\texttt{(),[],(()),([]),()[],()[()]}$
而下面这些不是正规括号序列：
$\texttt{(,[,),)(,([)],([]}$
给你一些含有字符 $\texttt($、$\texttt)$、$\texttt[$、$\texttt]$ 的括号序列。你需要找一个最短的正规括号序列，使给定括号序列作为一个子序列包含在其中。
输入格式
输入第一行为一个正整数，代表数据组数。每组数据内容见下文。这一行之后跟着一个空行，每两组数据中间也有一个空行。
每一组数据的输入都有且只有一行，最多包含 $100$ 个字符，这些字符只由括号（字符 $\texttt($、$\texttt)$、$\texttt[$、$\texttt]$）组成，任意两个括号之间没有空格。
输出格式
对于每一组数据，格式必须符合如下：
输出最短的括号序列，满足题目描述，并且每两个输出之间必须有一个空行分开，特别的，最后一个输出后也需要一个空行，也即最后一行是空行。