括号匹配相信大家都知道,比如: "()()" 和 "(())"都是正确匹配的括号串,而")(", "(" 和 ")"等都不是匹配的括号串。
现给我们一个长度为n,仅由’(‘ 和 ‘)’这两种括号组成的字符串s,我们的任务是确定是否可以找到一个长度为2n的括号串t,且满足以下两个条件:
(1)串t是一个匹配的括号串;
(2)串s不是串t的一个连续子串。
括号匹配相信大家都知道,比如: "()()" 和 "(())"都是正确匹配的括号串,而")(", "(" 和 ")"等都不是匹配的括号串。
现给我们一个长度为n,仅由’(‘ 和 ‘)’这两种括号组成的字符串s,我们的任务是确定是否可以找到一个长度为2n的括号串t,且满足以下两个条件:
(1)串t是一个匹配的括号串;
(2)串s不是串t的一个连续子串。
输出共t组。如果能够找到一个长度为2*|s|的正确匹配的括号串t,且s不是t的连续子串,则第一行输出:YES,第二行输出所找到的串t,否则仅一行输出:NO。
4 )( (() () ))()
YES (()) YES ()()() NO YES ()(()())
测试2输入:
4
))))))))())()(()))()((())()))()())(()))((()(()(())
)()))())(())))(())()())())(((()())()())(()()(()(((
()(()))()))()))(())()))(()()))()()(((((()(()()()((
((()())()))())))))())()))())))))))((()()(())()((()
测试2输出:
YES
()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()
YES
(((((((((((((((((((((((((((((((((((((((((((((((((())))))))))))))))))))))))))))))))))))))))))))))))))
YES
(((((((((((((((((((((((((((((((((((((((((((((((((())))))))))))))))))))))))))))))))))))))))))))))))))
YES
()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()