PythonでUnixスタイルのパスを解決するプログラムの書き方

問題の概要

文字列のリストとして与えられたUnix形式のパスについて、その解決済み（正規化）の結果を求めることを考えます。

Unixでは、「..」はひとつ前の（親）ディレクトリへ移動することを表し、「.」は現在のディレクトリに留まることを表します。ここでいう「解決」とは、これらの特殊な記号を評価し、最終的にどのディレクトリにいるのかを求める処理のことです。

たとえば、入力が次の場合を考えてみましょう。

path = ["usr", "..", "usr", ".", "local", "etc", "foo"]

このパスは「/usr/../usr/./local/etc/foo」を表しており、解決すると「/usr/local/etc/foo」になります。したがって、期待される出力は ['usr', 'local', 'etc', 'foo'] です。

解決のためのアルゴリズム

この問題は、スタックのような考え方を使うことでシンプルに解けます。手順は以下の通りです。

• 空のリスト s を用意する
• path 内の各要素 i について以下を繰り返す
  • i が「..」の場合：s が空でなければ、s の末尾の要素を削除する（1階層上へ戻る）
  • それ以外で、i が「.」でない場合：i を s の末尾に追加する
• 最後に s を返す

ポイントは、「..」が出てきたときに直前のディレクトリを取り消す操作が、まさにスタックのポップ操作に対応している点です。また「.」は何もしないため、単にスキップすればよいことになります。

実装例

それでは、実際のPythonコードを見てみましょう。

class Solution:
    def solve(self, path):
        s = []
        for i in path:
            if i == '..':
                # ひとつ前のディレクトリへ戻る
                if len(s) > 0:
                    s.pop()
            elif i != '.':
                # 通常のディレクトリ名なら追加
                s.append(i)
        return s

ob = Solution()
print(ob.solve(["usr", "..", "usr", ".", "local", "etc", "foo"]))

入力

["usr", "..", "usr", ".", "local", "etc", "foo"]

出力

['usr', 'local', 'etc', 'foo']

コードの解説

このコードでは、リスト s をスタックとして利用しています。各要素を先頭から順に処理していき、通常のディレクトリ名であれば append() で積んでいきます。「..」に出会ったときは pop() を呼び出して直前のディレクトリを取り除き、「.」に出会ったときは何もせずに次へ進みます。

すべての要素を処理し終えた時点で、リスト s に残っている要素がまさに解決後のパス構成要素となります。なお、ルートより上には移動できないため、s が空の状態で「..」が来た場合は無視するのが一般的です。

計算量はパスの要素数を n とすると O(n) となり、非常に効率的な処理です。