← 返回题目列表

AtCoder · abc394_d

G. 彩色括号序列

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

分数: 400 点

问题陈述

给你一个字符串 S 由六种字符组成: 如果 (, ), [, ], <, >.

一个字符串 T 满足以下条件,则称为彩色括号序列:

可以转动 通过重复以下操作任意次数(可能为零)将 T 转换为空字符串:

  • 如果存在连续的子串 T 这是其中之一 (), [],或 <>,选择一个这样的子字符串并将其删除。
  • 如果删除的子字符串位于开头或结尾 T,余数成为新的 T.
  • 否则,将删除的子字符串之前的部分和删除的子字符串之后的部分连接起来,成为新的 T.

判断是否 S 是一个彩色括号序列。

约束

  • S 是长度介于 1 和 2\times 10^5,包括在内。
  • S 包括 (, ), [, ], <, >.

输入

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

S

输出

If S 是一个彩色括号序列,打印 Yes;否则,打印 No.


示例输入 1

([])<>()

示例输出 1

Yes

对于 S=([])<>(),可以通过重复如下操作将其变成空字符串:

  • 删除子字符串 [] 从第二个到第三个字符 ([])<>(),然后连接其前后的部分。字符串变成 ()<>().
  • 删除子字符串 () 从第 1 个字符到第 2 个字符 ()<>()。字符串变成 <>().
  • 删除子字符串 <> 从第 1 个字符到第 2 个字符 <>()。字符串变成 ().
  • 删除子字符串 () 从第 1 个字符到第 2 个字符 ()。字符串变为空。

因此, S=([])<>() 是一个彩色括号序列,因此打印 Yes.


示例输入 2

([<)]>

示例输出 2

No

自从 S=([<)]> 不包含 (), [],或 <> 作为连续的子字符串,我们无法执行第一个操作,特别是 S 不是彩色括号序列。因此,打印 No.


示例输入 3

())

示例输出 3

No

无法转动 通过重复操作将 S 转换为空字符串。
因此, S 不是彩色括号序列,因此打印 No.