颠倒括在Python中括号内的子字符串的程序

假设我们有一个小写的字符串s，其中包含字母和括号“（”和“）”。我们必须以递归的方式反转括号中的每个字符串，并返回结果字符串。

因此，如果输入类似于s =“ back(aps)ce”，则输出将为“ backspace”。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个功能trav()。这将需要s，dir，start，close：= close，ans：= ans

• 如果s [start]与其他相同，则

• 除此以外，

• trav（s，-dir，close [other，start]-dir）

• 开始：=关闭[其他，开始] +目录

• 在ans的末尾插入s [start]

• 开始：=开始+目录

• end：=“（”如果dir与−1相同，否则为“）”

• 其他：=“（”如果结尾与“）”相同，否则为“）”

• 当start <s的大小，并且s [start]与end不同时，执行

• 在主要功能中，执行以下操作-

• ans：=一个新列表

• close：=一个包含键“）”和“（”）的新映射，初始值是两个空映射

• 堆栈：=一个新列表

• 对于s中的每个索引I和值c，

• o：=堆栈顶部，然后从堆栈中弹出

• close [“）”，i]：= o

• close [“（”，o]：= i

• 将我推入堆栈

• 如果c与“（”相同，则

• 否则，当c与“）”相同时，则

• 穿越(s,1,0)

• 返回用空白字符串连接的ans

让我们看下面的实现以更好地理解-

示例

class Solution:
   def solve(self, s):
      ans = []
      close = {")": {}, "(": {}}
      stack = []
      for i, c in enumerate(s):
         if c == "(":
            stack.append(i)
         elif c == ")":
            o = stack.pop()
            close[")"][i] = o
            close["("][o] = i
      def trav(s, dir, start, close=close, ans=ans):
         end = "(" if dir == -1 else ")"
         other = "(" if end == ")" else ")"
         while start < len(s) and s[start] != end:
            if s[start] == other:
               trav(s, −dir, close[other][start] − dir)
               start = close[other][start] + dir
            else:
               ans.append(s[start])
               start += dir
      trav(s, 1, 0)
      return "".join(ans)
ob = Solution()
print(ob.solve("back(aps)ce"))

输入值

"back(aps)ce"

backspace