← 返回题目列表

Codeforces · 2110/B

B. 带括号的向下

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

2077 年,机器人决定一劳永逸地摆脱平衡括号序列!

括号序列称为 平衡 如果它可以通过以下形式语法构造。

  1. 空序列 $$$\varnothing$$$ 是平衡的。
  2. 如果括号序列 $$$A$$$ 是平衡的,则 $$$\mathtt{(}A\mathtt{)}$$$ 也是平衡的。
  3. 如果括号序列 $$$A$$$ 和 $$$B$$$ 是平衡的,则串联序列 $$$A B$$$ 也是平衡的。

你是对抗平衡括号序列的部门负责人,你的主要任务是确定哪些括号可以破坏,哪些不能破坏。

给你一个平衡的括号序列,由字符串 $$$s$$$ 表示,由字符组成 ( 和 )。由于机器人的能力不是无限的,它们可以移除 正是 一个开口支架和 正是 字符串中的一个右括号。

你的任务是确定机器人是否可以删除这样两个括号,从而使字符串 $$$s$$$ 不再是平衡的括号序列。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例都包含一个字符串 $$$s$$$ ($$$2 \leq |s| \leq 2 \cdot 10^5$$$) - 字符序列 ( 和 ).

保证$$$s$$$ 是一个平衡的括号序列。

还保证所有测试用例的 $$$|s|$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出“是“如果机器人可以使字符串不再是平衡的括号序列,并且”NO”否则。

您可以以任何大小写(小写或大写)输出每个字母。例如,字符串“是", "是的", "是“,和”是”将被接受为肯定答案。

示例

输入
复制

4
(())
(())()()
()
(())(())

输出
复制

NO
YES
NO
YES

注意

在第一个测试用例中,可以表明机器人将无法打破正确的括号序列。

在第二个测试用例中,删除括号的选项之一如下:

$$$\texttt{(())}\color{red}{\texttt{(}}\texttt{)(}\color{red}{\texttt{)}} \rightarrow \texttt{(()))(}$$$,这不是正确的括号序列。

在第四个测试用例中,删除的选项之一如下:

$$$\texttt{(}\color{red}{\texttt{(}}\texttt{))((}\color{red}{\texttt{)}}\texttt{)}\rightarrow \texttt{())(()}$$$,这不是正确的括号序列。