Pythonで角かっこで囲まれた部分文字列を逆にするプログラム

文字と括弧「（」と「）」を含む小文字の文字列sがあるとします。括弧で囲まれたすべての文字列を再帰的に反転し、結果の文字列を返す必要があります。

したがって、入力がs ="back（aps）ce"のような場合、出力は「バックスペース」になります。

これを解決するには、次の手順に従います-

• 関数trav（）を定義します。これには、s、dir、start、close：=close、ans：=ans

  が必要です。

  • end：="（" dirが-1と同じ場合、それ以外の場合は "）"

  • other：="（"終了が "）"と同じ場合、それ以外の場合 "）"

  • start

    • s [start]が他と同じ場合、

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

      • start：=close [other、start] + dir

    • それ以外の場合

      • ansの最後にs[start]を挿入します

      • start：=start + dir

• 主な機能から、次のようにします-

• ans：=新しいリスト

• close：=キー「）」と「（」を含む新しいマップ最初の値は2つの空のマップです

• スタック：=新しいリスト

• sの各インデックスIと値cについて、実行します

  • cが"（"と同じ場合、

    • iをスタックにプッシュ

  • それ以外の場合、cが "）"と同じ場合、

    • o：=スタックの一番上、次にスタックからポップ

    • close ["）"、i]：=o

    • close ["（"、o]：=i

• trav（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