A173974.倒读便笺

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小林收到了一张特别的便笺。便笺上的字符串 ss 只包含小写英文字母和圆括号,圆括号可能嵌套出现。

便笺的阅读规则如下:

  1. 找到一对内部不再含有其他圆括号的匹配括号;
  2. 将这对括号内部的字母顺序翻转;
  3. 删除这对括号,保留翻转后的字母;
  4. 重复上述操作,直到字符串中不再含有圆括号。

如果同时存在多对可以处理的括号,可以先处理其中任意一对,最终结果相同。

保证字符串中的圆括号合法匹配,并且每对括号包围的范围内至少包含一个小写英文字母。这里的字母也可以位于更内层的括号中。

字符串可以不含圆括号,此时不需要进行任何操作。

请你输出按照上述规则处理后得到的字符串。

输入格式

输入一行字符串 ss。

输出格式

输出一行,表示处理后得到的字符串。

输入输出样例

  • 输入#1

    ab(cd(ef)g)h

    输出#1

    abgefdch
  • 输入#2

    (ab)cd(ef)

    输出#2

    bacdfe

说明/提示

样例解释 1

先处理内层括号,将其中的 efef 翻转为 fefe,字符串变为:

ab(cdfeg)h

再将外层括号中的 cdfegcdfeg 翻转为 gefdcgefdc,并删除括号,最终得到 abgefdchabgefdch。

样例解释 2

两对括号之间没有嵌套关系。分别将 abab 和 efef 翻转为 baba 和 fefe,中间的 cdcd 不变。

数据范围

对于所有测试数据,保证:

  • 1≤∣s∣≤20001\le |s|\le 2000,其中 ∣s∣|s| 表示字符串长度,括号也计入长度;
  • ss 仅包含小写英文字母、左圆括号和右圆括号;
  • 圆括号合法匹配;
  • 每对括号包围的范围内至少包含一个小写英文字母;
  • 圆括号的最大嵌套深度不超过 100100。

一对不在其他括号内部的括号深度为 11;每向内嵌套一层,深度增加 11;没有括号时,深度为 00。

输入解题思路,AI测评打分。不知道怎么写?

首页