问题 4189 --括号匹配

4189: 括号匹配★

时间限制: 1 Sec  内存限制: 128 MB
提交: 180  解决: 144
[提交][状态][命题人:]

题目描述

用以下方式定义合法的括号字符串

1.空串是合法的
2. 如果S是合法的, 那么(S)和[S]也都是合法的
3. 如果A和B是合法的, 那么AB是一个合法的字符串.

举个栗子, 下列字符串都是合法的括号字符串:

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

下面这些不是:

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

给出一个由字符'(', ')', '[', 和']'构成的字符串. 你的任务是找出一个最长的合法字符串的长度，使这个的字符串是给出的字符串的子序列。对于字符串a1 a2 ... an, b1 b2 ... bm 当且仅当对于1 = i1 < i2 < ... < in = m, 使得对于所有1 = j = n，aj = bij时, aj是bi的子序列

输入

多组数据. 每组数据在一行上输入一个只含有'(', ')', '[', ']'字符的字符串，字符串的最大长度是100, 输入字符串"end"结束

输出

对于每组数据, 在单独的一行上输出题目描述中所求的长度
样例输入
Copy
((()))
()()()
([]])
)[)(
([][][)
end
样例输出
Copy
6
6
4
0
6

提示

来源

POJ-2955 

[提交][状态]