作用域

题目描述

由小写英文字母、( 和 ) 组成的字符串,如果能通过以下步骤变为空字符串,则称其为「好字符串」:

• 首先,移除所有小写英文字母。
• 然后,在还能移除时,反复移除相邻的 ()。

例如,((a)ba) 是好字符串,因为移除所有小写英文字母后得到 (()),从中可以移除第 2 个和第 3 个字符处的相邻 () 得到 (),再进一步可以得到空字符串。

给定一个好字符串 $S$。用 $S_i$ 表示 $S$ 的第 $i$ 个字符。

对于每个小写英文字母 a、b、$\ldots$、z,我们都有一个写有该字母的球。此外,还有一个空箱子。

对于 $i = 1,2,\ldots,|S|$,按此顺序,高桥君执行以下操作(除非他昏倒):

• 如果 $S_i$ 是小写英文字母,则将写有该字母的球放入箱子。如果该球已经在箱子中,则他昏倒。
• 如果 $S_i$ 是 (,则不执行任何操作。
• 如果 $S_i$ 是 ),则取小于 $i$ 的最大整数 $j$,使得 $S$ 的第 $j$ 个到第 $i$ 个字符构成好字符串(可以证明这样的整数 $j$ 总是存在),并将第 $j$ 次到第 $i$ 次操作中放入箱子的所有球全部取出。

判断高桥君能否在不昏倒的情况下完成整个操作序列。

输入格式

输入按以下格式从标准输入给出:

$S$

输出格式

如果他能不昏倒地完成操作序列,则输出 Yes;否则输出 No。

样例

((a)ba)

Yes

对于 $i = 1$,他不执行任何操作。

对于 $i = 2$,他不执行任何操作。

对于 $i = 3$,他将写有 a 的球放入箱子。

对于 $i = 4$,$j=2$ 是小于 $4$ 的最大整数,使得 $S$ 的第 $j$ 个到第 $4$ 个字符构成好字符串,因此他从箱子中取出写有 a 的球。

对于 $i = 5$,他将写有 b 的球放入箱子。

对于 $i = 6$,他将写有 a 的球放入箱子。

对于 $i = 7$,$j=1$ 是小于 $7$ 的最大整数,使得 $S$ 的第 $j$ 个到第 $7$ 个字符构成好字符串,因此他从箱子中取出写有 a 的球和写有 b 的球。

因此,本题的答案是 Yes。

(a(ba))

No

对于 $i = 1$,他不执行任何操作。

对于 $i = 2$,他将写有 a 的球放入箱子。

对于 $i = 3$,他不执行任何操作。

对于 $i = 4$,他将写有 b 的球放入箱子。

对于 $i = 5$,写有 a 的球已经在箱子中,因此他昏倒,操作序列中止。

因此,本题的答案是 No。

(((())))

Yes

abca

No

数据范围

• $1 \le |S| \le 3 \times 10^5$
• $S$ 是好字符串。