分数: 550 点
问题陈述
给你一个字符串 S = S_1 S_2 S_3 \dots S_{|S|} 由大小写英文字母组成, (,和 ).
字符串中的括号 S 正确匹配。
重复以下操作,直到无法执行更多操作:
- 首先,选择一对整数 (l, r) 满足以下所有条件:
- l < r
- S_l =
( - S_r =
) - 每个字符 S_{l+1}, S_{l+2}, \dots, S_{r-1} 是大写或小写英文字母。
- 让 T = \overline{S_{r-1} S_{r-2} \dots S_{l+1}}.
- 在这里, \overline{x} 表示通过切换每个字符的大小写得到的字符串 x (大写到小写,反之亦然)。
- 然后,删除 l-th 通过 r第一个字符 S 并插入 T 位于删除发生的位置。
请参阅示例输入和输出以进行说明。
可以证明,可以去除所有 (和
使用上述操作从字符串中生成 ),最终的字符串与操作的执行方式和顺序无关。
确定最终字符串。
中的括号是什么意思 S 是否正确匹配?
首先,正确的括号序列定义如下:- 正确的括号序列是满足以下条件之一的字符串:
- 这是一个空字符串。
- 存在正确的括号序列 A,字符串是通过连接形成的
(, A,)按此顺序。 - 存在非空正确括号序列 A 和 B,字符串是通过连接形成的 A 和 B 按此顺序。
(和
使用上述操作从字符串中生成 )提取自 S 在不改变顺序的情况下形成了正确的括号序列。
约束
- 1 \le |S| \le 5 \times 10^5
- S 由大小写英文字母组成,
(,和). - 中的括号 S 正确匹配。
输入
输入由标准输入按以下格式给出:
S
输出
打印最终的字符串。
示例输入 1
((A)y)x
示例输出 1
YAx
让我们执行以下操作 S = ((A)y)x.
- 选择 l=2 和 r=4。子串
(A)被删除并替换为a.- 此操作后, S =
(ay)x.
- 此操作后, S =
- 选择 l=1 和 r=4。子串
(ay)被删除并替换为YA.- 此操作后, S =
YAx.
- 此操作后, S =
去掉括号后,字符串变成 YAx,应打印。
示例输入 2
((XYZ)n(X(y)Z))
示例输出 2
XYZNXYZ
让我们执行以下操作 S = ((XYZ)n(X(y)Z)).
- 选择 l=10 和 r=12。子串
(y)被删除并替换为Y.- 此操作后, S =
((XYZ)n(XYZ)).
- 此操作后, S =
- 选择 l=2 和 r=6。子串
(XYZ)被删除并替换为zyx.- 此操作后, S =
(zyxn(XYZ)).
- 此操作后, S =
- 选择 l=6 和 r=10。子串
(XYZ)被删除并替换为zyx.- 此操作后, S =
(zyxnzyx).
- 此操作后, S =
- 选择 l=1 和 r=9。子串
(zyxnzyx)被删除并替换为XYZNXYZ.- 此操作后, S =
XYZNXYZ.
- 此操作后, S =
去掉括号后,字符串变成 XYZNXYZ,应打印。
示例输入 3
(((()))(()))(())
示例输出 3
最终结果可能是空字符串。
示例输入 4
dF(qT(plC())NnnfR(GsdccC))PO()KjsiI((ysA)eWW)ve
示例输出 4
dFGsdccCrFNNnplCtQPOKjsiIwwEysAve