题目描述

“正则括号”序列的定义如下。

• 空序列是一个正则括号序列。
• 若$s$ 是正则括号序列，则$($$s$ $)$和[$s$ ]也是正则括号序列。
• 若$a$ 和$b$ 是正则括号序列，则$a$$b$ 也是正则括号序列。
• 没有其他序列是正则括号序列。

例如，$($ $)$、[]、$($ $($ $)$ $)$、$($ $)$ []、$($ $)$ [$($ $)$ ]都是正则括号序列，而$($、]、$)$ $($、$($ [$)$ ]、$($ [$($ ]不是正则括号序列。 给定括号序列$a_1 a_2 …a_n$ ，求解其最长的正则括号子序列的长度。也就是说，希望找到最大的$m$ ，使$a_{i 1} a_{i 2} …a_{im}$是一个正则括号序列，其中$1≤i_1 <i_2 <…<i_m ≤n$。例如给定初始序列$( [( [] ] ) ]$，最长的正则括号子序列是$[( [] ) ]$，其长度是$6$。

输入格式

输入包含多个测试用例。每个测试用例都只包含一行由$($、$)$、[、]组成的字符串，其长度为$1$～$1$$0$$0$$（$包括$1$和$1$$0$$0$$）$。输入的结尾由包含“$e$$n$$d$”的行标记，不应对其进行处理。

输出格式

对每个测试用例，都单行输出最长的正则括号子序列的长度。

样例

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

6
6
4
0
6

来源

POJ2955