← 返回题目列表

Codeforces · 1709/C

C. 恢复 RBS

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

括号序列是仅包含字符“(”和“)”的字符串。常规括号序列(或者简称为 RBS)是可以通过在序列的原始字符之间插入字符“1”和“+”来转换为正确的算术表达式的括号序列。例如:

- 括号序列“()()”和“(())”是正则表达式(结果表达式为:“(1)+(1)”和“((1+1)+1)”);
- 括号序列“)(”、“(”和“)”不是。

有苏格兰皇家银行。一些括号已替换为问号。是否真的有一种独特的方法可以用括号替换问号,从而得到的序列是 RBS?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — 测试用例的数量。

每个测试用例的唯一行包含一个 RBS,其中一些括号替换为问号。每个字符都是“(”、“)”或“?”。可以从给定序列中恢复至少一个RBS。

所有测试用例的序列总长度不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果用括号替换问号(以便生成的序列是 RBS)的方式是唯一的,则打印“YES”。如果有不止一种方式,则打印“NO”。

示例

输入 #1

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

输出 #1

YES
NO
YES
YES
NO

注意

在第一个测试用例中,唯一可能的原始 RBS 是“(())”。

在第二个测试用例中,有多种方法可以恢复 RBS。

在第三个和第四个测试用例中,唯一可能的原始 RBS 是“()”。

在第五个测试用例中,原始 RBS 可以是“((()()))”或“(())()()”。