欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~

问题 1083. -- 锘爷与括号

1083: 锘爷与括号

时间限制: 1 Sec  内存限制: 128 MB
提交: 136  解决: 59
[提交][状态][讨论版]

题目描述

数据结构老师给了锘爷一个长度为n的字符串,该串仅由( 和 ) 组成,比如((()))(((,
老师想让锘爷求所有括号都匹配的最长的子序列的长度。  输出最长子序列的长度即可。
这个问题显然难不倒锘爷,不幸的是锘爷又与妹子一块出去玩了(不要问锘爷去干什么了), 所以想让你帮忙解决这个问题。

匹配的定义为:
(1)空串是匹配的。
(2)若A是匹配的,则(A)是匹配的。
(3)若A、B是匹配的,则AB是匹配的。
例如() ()() (())()都是匹配的。
子序列的定义为:某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置(在前或在后)而形成的新序列。

输入

第一行整数T,代表数据组数(T不超过100)
接下来T行,每行一个字符串S, 长度不超过201508

输出

如果不存在匹配的子序列输出0, 否则输出满足条件的最长子序列的长度,每组输出占一行。

样例输入

2
())(())(())(
)(

样例输出

10
0

提示

来源

[提交][状态][讨论版]