问题 6584 --括号匹配

6584: 括号匹配★★

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

题目描述

       括号匹配相信大家都知道,比如: "()()" 和 "(())"都是正确匹配的括号串,而")(",  "(" 和 ")"等都不是匹配的括号串。

现给我们一个长度为n,仅由’(‘ 和 ‘)’这两种括号组成的字符串s,我们的任务是确定是否可以找到一个长度为2n的括号串t,且满足以下两个条件:

1)串t是一个匹配的括号串;

2)串s不是串t的一个连续子串。

输入

第一行包含一个整数t(1≤t≤1000)——测试用例的数量。

每个测试用例一行一个字符串s(2<=|s|<=50|s|表示串s的长度),串s仅由’(‘ /或 ‘)’这两种括号组成。

输出

       输出共t组。如果能够找到一个长度为2*|s|的正确匹配的括号串t,且s不是t的连续子串,则第一行输出:YES,第二行输出所找到的串t,否则仅一行输出:NO

样例输入
Copy
4
)(
(()
()
))()
样例输出
Copy
YES
(())
YES
()()()
NO
YES
()(()())

提示

测试2输入:

4
))))))))())()(()))()((())()))()())(()))((()(()(())
)()))())(())))(())()())())(((()())()())(()()(()(((
()(()))()))()))(())()))(()()))()()(((((()(()()()((
((()())()))())))))())()))())))))))((()()(())()((()
测试2输出:

YES
()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()
YES
(((((((((((((((((((((((((((((((((((((((((((((((((())))))))))))))))))))))))))))))))))))))))))))))))))
YES
(((((((((((((((((((((((((((((((((((((((((((((((((())))))))))))))))))))))))))))))))))))))))))))))))))
YES
()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()


来源

 

[提交][状态]