括号补齐

Grade 0 Open Time Sunday, 10 July 2011, 8:50 am
Discount 0.8 Time Discount Sunday, 10 July 2011, 8:50 am
Allow late Yes Close Time Sunday, 10 July 2011, 8:50 am
Input file bracket.in Output file bracket.out

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

1 . 空序列是规则序列;

2 . 如果 S 是规则序列,那么( S )和 [S] 也是规则序列;

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

例如,下面的字符串都是规则序列:

() , [] , (()) , ([]) , ()[] , ()[()]

这几个则不是:

(, [ , ] ,)(,()),( [ ()

编程任务:

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

说明:

1、 对于序列 a1a2...an 和序列 b1b2...bm ,如果存在一组下标 1 ≤ i1 < i2 < ... < in ≤ m ,使得 aj=bij 对一切 1 ≤ j ≤ n. 成立,那么 a1a2...an 就叫做 b1b2...bm 的子列。

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、 考虑到这里面肯定会有很多的子问题重复计算的问题,所以我们可以用数组保存中间计算结果,尽量减少算法复杂度。