[ABC350] F - Transpose

F - Transpose

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 550 分

题面

给定一个包含大写字母、小写字母、( 和 ) 的字符串 。
字符串 中的括号是正确匹配的。

重复以下操作直到无法继续为止：

• 首先，选择一对满足以下所有条件的整数对 ：
  • (
  • )
  • 中的每个字符都是大写或小写英文字母。
• 令 。
  • 这里， 表示将 中每个字符的大小写进行切换（大写变小写，小写变大写）所得到的字符串。
• 然后，删除字符串 的第 至第 个字符，并在删除位置插入 。

参考示例输入和输出以获得更清晰的解释。

可以证明通过上述操作可以将字符串中的所有 ( 和 ) 移除，并且最终字符串的结果与操作的方式和顺序无关。
确定最终字符串是什么。

中的括号正确匹配是什么意思？首先，定义如下的正确括号序列：

• 一个正确括号序列是一个满足以下条件之一的字符串：
  • 它是一个空字符串。
  • 存在一个正确括号序列 ，并以 (、、) 的顺序连接形成该字符串。
  • 存在非空的正确括号序列 和 ，并以 和 的顺序连接形成该字符串。

当且仅当从字符串 中提取 ( 和 ) 而不改变顺序形成一个正确的括号序列时， 中的括号才是正确匹配的。

限制条件

• 包含大写字母、小写字母、( 和 )。
• 中的括号是正确匹配的。

---

输入

输入由标准输入给出，格式如下：

输出

打印最终字符串。

---

输入样例 1

((A)y)x

输出样例 1

YAx

对于 ((A)y)x，我们进行如下操作：

• 选择 和 。字符串 (A) 被替换为 a。
  • 完成操作后， (ay)x。
• 选择 和 。字符串 (ay) 被替换为 YA。
  • 完成操作后， YAx。

移除括号后，字符串变为 YAx，需要输出。

---

输入样例 2

((XYZ)n(X(y)Z))

输出样例 2

XYZNXYZ

对于 ((XYZ)n(X(y)Z))，我们进行如下操作：

• 选择 和 。字符串 (y) 被替换为 Y。
  • 完成操作后， ((XYZ)n(XYZ))。
• 选择 和 。字符串 (XYZ) 被替换为 zyx。
  • 完成操作后， (zyxn(XYZ))。
• 选择 和 。字符串 (XYZ) 被替换为 zyx。
  • 完成操作后， (zyxnzyx)。
• 选择 和 。字符串 (zyxnzyx) 被替换为 XYZNXYZ。
  • 完成操作后， XYZNXYZ。

移除括号后，字符串变为 XYZNXYZ，需要输出。

---

输入样例 3

(((()))(()))(())

输出样例 3

最终结果可能是一个空字符串。

---

输入样例 4

dF(qT(plC())NnnfR(GsdccC))PO()KjsiI((ysA)eWW)ve

输出样例 4

dFGsdccCrFNNnplCtQPOKjsiIwwEysAve