OI题库

【题目描述】

定义如下规则序列(字符串)：

1．空序列是规则序列；

2．如果S是规则序列，那么(S)和[S]也是规则序列；

3．如果A和B都是规则序列，那么AB也是规则序列。

例如，下面的字符串都是规则序列：

()，[]，(())，([])，()[]，()[()]

而以下几个则不是：

(，[，]，)(，())，([()

    现在，给你一些由‘(’，‘)’，‘[’，‘]’构成的序列，你要做的，是找出一个最短规则序列，使得给你的那个序列是你给出的规则序列的子列。(对于序列a1，a2，…，an和序列bl，b2，…，bn，如果存在一组下标1≤i12<…<in≤m，使得aj＝bij对一切1≤j≤n成立，那么a1，a2…，an就叫做b1，b2，…，bn的子列。

【输入格式】

输入文件仅一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，长度不超过100。

【输出格式】

输出文件也仅有一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，把你找到的规则序列输出即可。因为规则序列可能不止一个，因此要求输出的规则序列中嵌套的层数尽可能地少。

【样例输入】

([()

【样例输出】

()[]()

最多的嵌套层数为1，如层数为2时的一种为()[()]