OI题库

定义如下规则序列（字符串）：

1 ． 空序列是规则序列；

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

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

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

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

这几个则不是：

（， [ ， ] ，）（，（）），（ [ （）

编程任务：

从输入文件中读入一个字符串，字符串由‘（’，‘）’，‘ [ ’，‘ ] ’构成的序列，你要做的，是找出一个最短规则序列，使得给你的那个序列是你给出的规则序列的子列，并将结果写在输出文件中。

说明：

1、 对于序列 a₁a₂...a_n 和序列 b₁b₂...b_m ，如果存在一组下标 1 ≤ i₁ ＜ i₂ ＜ ... ＜ i_n ≤ m ，使得 a_j=b_ij 对一切 1 ≤ j ≤ n. 成立，那么 a₁a₂...a_n 就叫做 b₁b₂...b_m 的子列。

2、 有多种最短匹配方式时，取嵌套数最少的匹配方式，例如 : ][( 最短的匹配方式有 [][()] 和 [][]() 两种，则取后面的这种情况，即 [][]() ，因为它的嵌套数最少。

输入

输入文件 (bracket.in) 仅一行，全部由‘（’，‘）’，‘ [ ’，‘ ] ’组成，没有其它字符，长度不超过 100 。

输出

输出文件 (bracket.out) 也仅有一行，全部由‘（’，‘）’，‘ [ ’，‘ ] ’组成，没有其它字符，把你找到的规则序列输出即可。

样例

bracket.in

（ [ （）

bracket.out

（） [ （） ]

解答提示 :

1、 大前提是补全后的括号系列长度最短，小前提是要求嵌套数最少。

所以原给出括号系列中能成对的括号尽量安排内部配对消化掉，内部实在是没有配才额外补充配对，例如：原系列是 ([(], 则匹配步骤为：先为第 1 个字符找对象，一直枚举完整个系列都没有找到对象，根据要求嵌套数最少的原则，应当先给它配对后再去完成剩余的系列 [(] ，剩下的系列第一个括号是 [ ，发现它在后面的括号里面有一个配对的 ] ，因为长度小比嵌套少更需要优先考虑，所以肯定是将它们两个配对，剩下 ( 配对就简单了，所以最终的配对结果是： ()[()]

2、 考虑到大问题划分成多个小问题的方式：原问题是 ([(] ，我们应当根据实际

情况将它划分为：“ ( ”和“ [(] ”，前者很好解决，后者在寻找匹配后，划分为 [+ “ ( ” +] 的子问题的形式。然后再将子问题“ ( ”求解后再合并就行了，完全类似分而治之，再合并成果的方式。

3、 一般情况：上面是具体的实例分析，现在我们再回到一般情况：

假设我们要处理的是串中的起点 l 与终点 r 之间的部分，即 a[l]…a[r] ，则我们从 a[l+1] 开始去寻找与它匹配的“另一半”：

假如找到，是 a[k] ，则将 a[l]…a[r] 划分为： a[l]+ “ a[l+1]…a[k-1] ” +a[k]+ “ a[k+1]…a[r] ”，再分别处理子问题 ( 从 l+1 到 k-1) 和 ( 从 k+1 到 r) 即可。

假如没找到，则先直接将 a[l] 配好对，得到 a[l]+ 它的配对 + “ a[l+1]…a[r] ”，然后再处理后面的子问题 ( 从 l+1 到 r)

4、 还要注意的一个问题是 ] 和 ) 不能作为最后结果的起始符，所以如果我们发现它的起始符是这二者之一，则马上给他在前面额外补一个 [ 或者是 ( 给他配对好后再来处理后面剩余的系列。

5、 考虑到这里面肯定会有很多的子问题重复计算的问题，所以我们可以用数组保存中间计算结果，尽量减少算法复杂度。