Pythonでn(t)形式の文字列を展開・デコードするプログラムの実装方法

問題の概要

ある文字列 s が与えられ、これはより長い元の文字列をエンコードしたものだとします。n(t) という表記は「文字列 t を n 回繰り返して連結したもの」を意味し、t には通常の文字列だけでなく、別のエンコード済み文字列が再帰的に含まれることもあります。この記事では、エンコードされた文字列 s をデコード（展開）するPythonプログラムを紹介します。

たとえば、入力が s = "3(pi)2(3(am))0(f)1(u)" の場合、出力は "pipipiamamamamamamu" になります。「pi」が3回、「am」が6回（2×3）、「f」は0回のため無視され、「u」が1回繰り返された結果です。

解決アプローチ：再帰的なパース処理

この問題は、再帰下降パース（再帰的な構文解析）を使うことで効率的に解けます。全体の流れは次のとおりです。

1. 読み取り位置を示すインデックス i を 0 で初期化します。
2. 文字列を解析する関数 parse() を定義します。
3. 結果を一時的に保持するためのリスト ans を用意します。
4. i が文字列の長さ未満で、かつ s[i] が ")" ではない間、以下を繰り返します。
   • s[i] が数字の場合：
     • d を 0 で初期化し、s[i] が数字である限り「d = 10 × d + s[i] の整数値」で更新しながら i を進めます（これにより複数桁の回数にも対応できます）。
     • i を 1 つ進めて "(" を読み飛ばします。
     • segment = parse() を呼び出し、括弧の中身を再帰的に取得します。
     • i を 1 つ進めて ")" を読み飛ばします。
     • segment を d 回 ans に追加します。
   • それ以外の場合： s[i] を ans の末尾に追加し、i を 1 つ進めます。
5. ans の要素を連結した文字列を返します。

メイン側からは parse() の戻り値をそのまま返すだけです。

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

class Solution:
   def solve(self, s):
      i = 0

      def parse():
         nonlocal i
         ans = []
         while i < len(s) and s[i] != ")":
            if s[i].isdigit():
               # 数値部分を読み取る（複数桁対応）
               d = 0
               while s[i].isdigit():
                  d = 10 * d + int(s[i])
                  i += 1
               i += 1          # "(" をスキップ
               segment = parse()
               i += 1          # ")" をスキップ
               ans.extend(segment for _ in range(d))
            else:
               ans.append(s[i])
               i += 1
         return "".join(ans)

      return parse()

ob = Solution()
s = "3(pi)2(3(am))0(f)1(u)"
print(ob.solve(s))

入力

"3(pi)2(3(am))0(f)1(u)"

出力

pipipiamamamamamamu

ポイントまとめ

• 入れ子になった n(t) 構造は、再帰呼び出しによって自然に処理できます。
• 回数 n は必ずしも1桁とは限らないため、連続する数字をまとめて読み取る処理が必要です。
• n = 0 の場合は該当部分が出力に現れず、空文字列として扱われます。
• 計算量は出力文字列の長さにほぼ比例し、入力サイズに対して線形時間で動作します。