Pythonでスタック操作をシミュレートして最終結果を求める方法

文字列のリスト ops が与えられ、各要素は以下のいずれかの操作を表すとします。

• 非負の整数値: その値をスタックにプッシュする
• "POP": スタックの最上位要素を削除する
• "DUP": 最上位の要素をもう一度スタックに挿入し、複製する
• "+": 上位2つの要素をポップし、その合計値をスタックにプッシュする
• "-": 上位2つの要素をポップし、(最上位要素 − その直下の要素) の結果をスタックにプッシュする

すべての操作を適用した後の、スタックの最上位要素を求めるのが目的です。もし操作が無効な場合(たとえば空のスタックからPOPしようとした場合など)は -1 を返します。

動作例

入力が ops = ["5", "2", "POP", "DUP", "3", "+", "15", "-"] の場合、出力は 7 になります。

処理の流れを順に見てみましょう。

1. 最初の2つの操作で 5 と 2 をプッシュ → スタックは [5, 2]
2. POP で1つ削除 → スタックは [5]
3. DUP で 5 を複製 → スタックは [5, 5]
4. 3 をプッシュ → スタックは [5, 5, 3]
5. 「+」で加算 → スタックは [5, 8]
6. 15 をプッシュ → スタックは [5, 8, 15]
7. 「-」で減算(15 - 8)→ スタックは [5, 7]

したがって、最終的にスタックの最上位にある要素は 7 です。

解法のアプローチ

この問題は、リストを先頭から順に走査しながらスタックをシミュレートすることで解けます。手順は以下の通りです。

• 新しい空のスタックを用意する
• ops 内の各要素 i について以下を判定する
  • i が数値なら、それをスタックにプッシュする
  • スタックのサイズが1以上で i が "POP" なら、最上位要素を削除する
  • スタックのサイズが1以上で i が "DUP" なら、最上位要素を取り出して2回挿入する
  • スタックのサイズが2以上で i が "+" なら、上位2つの要素をポップし、その合計をプッシュする
  • スタックのサイズが2以上で i が "-" なら、上位2つの要素をポップし、(a - b) の差をプッシュする
  • 上記のどれにも当てはまらない場合は、無効な操作として -1 を返す
• すべての操作が完了したら、スタックの最上位要素を返す

Pythonでの実装例

以下が実際の実装コードです。

def solve(ops):
    stack = []
    for i in ops:
        if i.isnumeric() == True:
            stack.append(int(i))
        elif len(stack) >= 1 and i == "POP":
            stack.pop()
        elif len(stack) >= 1 and i == "DUP":
            p = stack.pop()
            stack.append(p)
            stack.append(p)
        elif len(stack) >= 2 and i == "+":
            a = stack.pop()
            b = stack.pop()
            stack.append(a + b)
        elif len(stack) >= 2 and i == "-":
            a = stack.pop()
            b = stack.pop()
            stack.append(a - b)
        else:
            return -1
    return stack.pop()

ops = ["5", "2", "POP", "DUP", "3", "+", "15", "-"]
print(solve(ops))

入力

["5", "2", "POP", "DUP", "3", "+", "15", "-"]

出力

7

計算量について

このアルゴリズムの時間計算量は O(n) です(n は操作の数)。各操作は定数時間で処理できるため、リストを一度走査するだけで済みます。空間計算量も O(n) で、スタックに保持される要素数に依存します。

注意点

• isnumeric() は文字列が数字であるかを判定しますが、負の数や小数には対応していません。必要に応じて例外処理を追加するとより堅牢になります。
• すべての操作を処理した後にスタックが空の場合も考慮すると、さらに安全な実装になります。