Problem5816--括号匹配

5816: 括号匹配

Time Limit: 1.000 Sec  Memory Limit: 128 MB
Submit: 11  Solved: 4
[Submit] [Status] [Web Board] [Creator:]

Description

我们给出"正则括号序列"的递归定义：
  • 空序列是正则括号序列，
  • 若s是正则括号序列，则(s)和[s
  • 若a和b都是正则括号序列，则ab也是正则括号序列。
  • 其他任何序列都不是正则括号序列
例如，以下字符序列都是正则括号序列：
(), [], (()), ()[], ()[()]
而以下字符序列则不是：
(, ], )(, ([)], ([(]
给定一个由字符a1a2 … an组成的括号序列，你的目标是找出作为s子序列的最长正则括号序列的长度。也就是说，你需要找到最大的m，使得存在下标i1, i2, …, im满足1 ≤ i1 < i2 < … < im ≤ n，且ai1ai2 … aim构成正则括号序列。
以初始序列([([]])]为例，其最长正则括号子序列是[([])]。

输入

输入文件包含多个测试用例。每个测试用例由一行字符组成，仅包含(、)、[和]；每个测试用例的长度在1到100之间（含边界）。文件末尾以单独一行"end"标记，该行无需处理。

输出

对于每个测试用例，程序应在单独一行输出可能的最长正则括号子序列的长度。

样例

Inputcopy Outputcopy 
((()))
()()()
([]])
)[)(
([][][)
end
 
6
6
4
0
6

Sample Input

((()))
()()()
([]])
)[)(
([][][)
end

Sample Output

6
6
4
0
6

Source/Category

 

[Submit] [Status]