#5039. 括号序列

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Laffey

题目描述

POJ 链接

注意:本题非原数据,在 HYOI 通过本题不代表能在其他 OJ 通过。


我们给出了“正则括号”序列的以下归纳定义:

  • 空序列是正则括号序列。
  • 如果 s 是正则括号序列,则 (s)[s] 是正则括号序列。
  • 如果 ab 是正则括号序列,则 ab 是正则括号序列。
  • 没有其他序列是正则括号序列。

例如,以下所有字符序列都是正则括号序列:

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

而以下字符序列不是:

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

给定一个字符序列 a_1a_2a_3 \ldots a_n ,找出一个最长的正则括号序列,该序列应为给定序列的子序列。输出它的长度。

输入格式

输入文件包含多组测试数据。每行包含一个仅由 (, ), [, ] 组成的字符串。字符串的长度 L 满足 1 \leq L \leq 100 。输入文件以一行 end 结束。

输出格式

对于每组测试数据,你的程序应输出一个数字,表示最长括号子序列的长度。

样例

样例输入

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

样例输出

6
6
4
0
6

数据范围与提示

对于所有测试点有 1 \leq L \leq 100

来源:Stanford Local 2004, Brackets