Pythonでランレングス符号化文字列をデコードするイテレータクラスの実装方法

問題の概要

ランレングス符号化（Run-Length Encoding）された小文字のみの文字列 s を受け取って初期化するイテレータクラスを定義することを考えます。このイテレータには、次の2つのメソッドを実装します。

• next()：イテレータ内の次の要素を1つ返します
• hasnext()：次の要素がまだ存在するかどうかを判定します

例えば、入力が s = "2b1a" の場合、この文字列でオブジェクトを生成し、next() → hasnext() → next() → next() → hasnext() の順に呼び出すと、出力は "b"、True、"b"、"a"、False となります。

解決のための手順

この問題は、以下の手順で解くことができます。

1. コンストラクタを定義します。引数として符号化済みの文字列 s を受け取ります。
2. output（新しいリスト）と num（空文字列）を用意します。
3. 文字列 s の各文字 i に対して処理を行います。
   • i がアルファベットの場合：num を整数に変換して output の末尾に追加し、続けて文字 i も追加します。その後、num を空文字列に戻します。
   • i が数字の場合：num に i を連結していきます（これにより「12」のような複数桁の数値にも対応できます）。
4. next() メソッドを定義します。hasnext() が真である場合、output の先頭から出現回数 count と文字 letter を取り出し、count を 1 減らします。減算後の count が 0 より大きければ output[0] を更新し、そうでなければ先頭の2要素（回数と文字のペア）をリストから削除します。最後に letter を返します。
5. hasnext() メソッドを定義します。output のサイズが 0 でなければ True を、空であれば False を返します。

実装例

以下の実装を見ると、より理解が深まります。

class RunLengthIterator:
    def __init__(self, s):
        self.output = []
        num = ""
        for i in s:
            if i.isalpha():
                self.output.append(int(num))
                self.output.append(i)
                num = ""
            else:
                num += i

    def next(self):
        if self.hasnext():
            count = self.output[0]
            letter = self.output[1]
            count -= 1
            if count > 0:
                self.output[0] -= 1
            else:
                self.output = self.output[2:]
            return letter

    def hasnext(self):
        if len(self.output) != 0:
            return True
        return False

s = "2b1a"
obj = RunLengthIterator(s)
print(obj.next())
print(obj.hasnext())
print(obj.next())
print(obj.next())
print(obj.hasnext())

入力

"2b1a"
obj = RunLengthIterator(s)
obj.next()
obj.hasnext()
obj.next()
obj.next()
obj.hasnext()

出力

b
True
b
a
False

動作のポイント

コンストラクタでは、符号化文字列を「出現回数」と「文字」が交互に並ぶリストへと展開しています。例えば "2b1a" なら [2, 'b', 1, 'a'] という形式になります。next() が呼ばれるたびに先頭のカウントを減らし、カウントが尽きたペアはリストから取り除くことで、元の文字列を1文字ずつ正しく復元できる仕組みです。各操作はリストの先頭部分のみを扱うため、シンプルでありながら効率的な実装になっています。