#P1235. 括号匹配
括号匹配
题目描述
括号匹配的相关规则如下:
- 空序列是常规括号序列。
- 如果
s
是常规括号序列,则(s)
和[s]
是常规括号序列,并且如果a
和b
是常规括号序列,则ab
是常规括号序列。 - 没有其他序列是常规括号序列。
例如,以下所有字符序列都是常规括号序列:
(),[],()[],()[()]
。
而以下字符序列不是:
(,],)(,([)],([(]
。
给定一个由字符 组成的括号字符序列 ,请你找到作为 子序列的最长的括号序列的长度。
例如给定初始序列([([]])]
,最长的正则括号子序列是[([])]
。
输入格式
输入包含多组数据,每组数据包含一行,输入的字符串长度小于等于 ,且只包含 (
,)
,[
,]
。
输入以一个字符串 end
结束。
输出格式
对于每组数据,输出一行,一个数字,表示最大长度。
样例 #1
((()))
()()()
([]])
)[)(
([][][)
end
6
6
4
0
6