Pythonで文字列コマンドのゴールパーサー解釈を求めるプログラム

ゴールパーサー(Goal Parser)とは

ゴールパーサーは、与えられた文字列コマンドを特定のルールに従って解釈するプログラムです。コマンドは以下の要素で構成されます。

• アルファベット「G」
• 開き括弧と閉じ括弧のペア「()」
• 「(al)」(これらが任意の順序で並びます)

ゴールパーサーは、これらを次のように解釈します。

• 「G」→ 文字列「G」
• 「()」→ 文字列「o」
• 「(al)」→ 文字列「al」

そして、解釈された文字列は元の出現順序のまま連結されます。つまり、文字列コマンドが与えられたとき、そのゴールパーサーによる解釈結果を求めるのがこの問題の目的です。

例えば、入力が command = "G()()()(al)(al)" の場合、出力は「Goooalal」となります。

解決のための手順

この問題を解くには、以下の手順に従います。

1. 空の文字列 s を用意します。
2. i を 0 から command の長さ - 1 まで繰り返します。
   • command[i] が「(」でも「)」でもない場合、s に command[i] を連結します。
   • command[i] が「(」であり、かつ command[i+1] が「)」であり、i+1 < len(command) を満たす場合、s に「o」を連結します。
   • command[i] が「(」の場合は、次の反復へ進みます。
   • command[i] が「)」の場合も、次の反復へ進みます。
3. 最後に s を返します。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

def solve(command):
    s = ""
    for i in range(len(command)):
        if command[i] != "(" and command[i] != ")":
            s += command[i]
        if command[i] == "(" and i + 1 < len(command) and command[i+1] == ")":
            s += "o"
        if command[i] == "(":
            continue
        if command[i] == ")":
            continue
    return s

command = "G()()()(al)(al)"
print(solve(command))

入力

"G()()()(al)(al)"

出力

Goooalal

別のアプローチ:replaceメソッドを活用する

実は、Pythonの文字列置換メソッド replace() を使えば、より簡潔に記述することもできます。

def solve(command):
    return command.replace("()", "o").replace("(al)", "al")

この方法では、パターン「()」と「(al)」が互いに重なり合わないため、置換の順序に関係なく正しい結果が得られます。計算量はいずれの方法も O(n) で、文字列の長さに対して線形時間で処理できます。