题目描述

我们按如下方式定义一个合法的括号序列：

1. 空序列是一个合法的括号序列。
2. 如果 $S$ 是一个合法的括号序列，那么 $(S)$ 和 $[S]$ 也都是合法的括号序列。
3. 如果 $A$ 和 $B$ 是合法的括号序列，那么 $AB$ （即 $A$ 和 $B$ 拼接而成的序列）也是合法的括号序列。

例如，以下所有字符序列都是合法的括号序列： $()$, $[]$, $(())$, $([])$, $()[]$, $()[()]$

而以下所有字符序列都不是合法的括号序列： $($, $[$, $)$, $)($, $([)]$, $([(]$

给定一个由字符$($, $)$, $[$, $]$ 组成的序列。你需要找到最短的合法括号序列，使得给定的字符序列是它的一个子序列。在这里，如果存在这样的索引 $1 = i1 < i2 <... < in = m$，使得对于所有 $1 = j = n$ 都有$aj = bij$，那么字符串 $a1 a2... an$ 就被称为字符串 $b1 b2... bm$ 的子序列。

输入格式

输入文件中最多包含 100 个括号（字符 $($, $)$, $[$, $]$），它们位于单独的一行中，且该行没有其他字符。

输出格式

向输出文件中写入一行内容，该行包含一个长度最短的合法括号序列，且给定的序列是它的一个子序列。

([(]

()[()]

来源

2001年东北欧地区