← 返回题目列表

Codeforces · 1469/A

A. 常规括号序列

中文机器翻译题面 查看原题

如果可以通过在序列中插入字符 + 和 1 来获得正确的算术表达式,则该括号序列称为正则序列。例如,序列 (())()、() 和 (()(())) 是规则的,而 )(、(() 和 (()))( 则不是。我们将规则的括号序列称为“RBS”。

给定一个由 $$$n$$$ 个字符 (, ) 和/或 ? 组成的序列 $$$s$$$。此序列中恰好有一个字符(并且恰好有一个字符)。

你必须替换每个字符?与 ) 或 ( (不同的字符 ? 可以用不同的括号替换)。您不能对字符重新排序、删除它们、插入其他字符,并且每个 ? 都必须被替换。

确定在这些替换后是否可以获得 RBS。

输入

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

每个测试用例由一行包含 $$$s$$$ ($$$2 \le |s| \le 100$$$) — 一系列字符 (, ) 和/或 ? 组成。此序列中恰好有一个字符(并且恰好有一个字符)。

输出

对于每个测试用例,如果可以获得常规括号序列,则打印 YES,否则打印 NO}。

您可以在任何情况下打印每个字母(例如,YES,Yes,yes,yE 都将被识别为肯定答案)。

示例

输入 #1

5
()
(?)
(??)
??()
)?(?

输出 #1

YES
NO
YES
YES
NO

注意

在第一个测试用例中,序列已经是 RBS。

在第三个测试用例中,您可以通过以下方式获取 RBS:()() 或 (())。

在第四个测试用例中,您可以获得RBS,如下所示:()()。