分数: 400 点
问题陈述
由小写英文字母组成的字符串, (,和 ) 据说是 好字符串 如果可以通过以下步骤将其设为空字符串:
- 首先,删除所有小写英文字母。
- 然后,重复删除连续的
()虽然可能。
例如, ((a)ba) 是一个很好的字符串,因为删除所有小写英文字母会产生 (()),我们可以从中删除连续的 () 在 2-nd 和 3-rd 获取的字符 (),最终以空字符串结束。
你得到了一个很好的字符串 S。 我们表示为 S_i 这 i- 第一个字符 S.
对于每个小写英文字母 a, b, \ldots,和 z,我们有一个球,上面写着字母。
此外,我们还有一个空盒子。
对于每个 i = 1,2, \ldots ,|S| 按照这个顺序,高桥会执行以下操作,除非他晕倒。
- If S_i 是一个小写英文字母,将写有字母的球放入盒子中。 如果球已经在盒子里,他就会晕倒。
- If S_i is
(,什么都不做。 - If S_i is
),取最大整数 j 小于 i 这样 j-th 通过 i第一个字符 S 形成良好的字符串。 (我们可以证明这样一个整数 j 始终存在。)从盒子中取出他放入盒子中的所有球 j-th 通过 i第次操作。
确定高桥是否可以在不晕倒的情况下完成一系列操作。
约束
- 1 \leq |S| \leq 3 \times 10^5
- S 是一个很好的字符串。
输入
输入由标准输入按以下格式给出:
S
输出
打印 Yes 如果他能够完成一系列操作而不晕倒;打印 No 否则。
示例输入 1
((a)ba)
示例输出 1
Yes
对于 i = 1,他什么也没做。
对于 i = 2,他什么也没做。
对于 i = 3,他将球放在
盒子里写着 a 。
对于 i = 4, j=2 是小于的最大整数 4 这样 j-th 通过 4第一个字符 S 形成一个良好的线,所以他用
盒子上写着 a 。
上面写着
对于 i = 5,他将球放在
盒子里写着 b 。
对于 i = 6,他将球放在
盒子里写着 a 。
对于 i = 7, j=1 是小于的最大整数 7 这样 j-th 通过 7第一个字符 S 形成一个良好的线,所以他用
盒子上写着 a ,另一个写着 b,来自盒子。
因此,本例的答案是 Yes.
示例输入 2
(a(ba))
示例输出 2
No
对于 i = 1,他什么也没做。
对于 i = 2,他将球放在
盒子里写着 a 。
对于 i = 3,他什么也没做。
对于 i = 4,他将球放在
盒子里写着 b 。
对于 i = 5,球与
上面写的 a 已经在盒子里了,所以他晕了过去,中止了操作顺序。
因此,本例的答案是 No.
示例输入 3
(((())))
示例输出 3
Yes
示例输入 4
abca
示例输出 4
No