Pythonで「スタック（Stack）」
はじめに
ここでは「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」の中で取り上げられている「AOJ (Aizu Online Judge」)の問題を自分で解いた際に学んだことや、こう考えれば分かりやすいと感じたことなどを自分への整理も兼ねてまとめています。
このテキストはC++で書かれているので、私のようにpythonで勉強をされている初学者の方の参考になれば幸いです。また私自身も初学者ゆえ、至らない点が多々あると思いますので、ご指摘・ご助言頂ければ喜びます。よろしくお願いします。
問題詳細
ALDS 1_3_A: Stack
スタックを利用して逆ポーランド記法の計算を行う問題です。
問題詳細は上記リンクをご参考ください
考え方
・後入れ先出しを利用して、演算子の手前二つの数値を計算します
pythonコード
from collections import deque
l = input().split()
st = deque() # dequeはスタック、キュー、デックに利用可能
for k in l:
if k in "+*-": # 演算子の場合は手前２つの数値を用いて演算を行う
n2 = st.pop()
n1 = st.pop()
st.append(str(eval(n1 + k + n2))) # 計算結果を再び入れる
else:
st.append(k) # 数値の場合はスタックに追加
print(st[0])
ポイント
・スタックとして扱うので、基本操作はpop()とappend()です。
・演算子が来た時に手前２つの数値を用いて計算するのですが、スタックから数値を取り出す順番は、計算を行う順番とは逆になるので（後入れ先出しだから）注意が必要です。
・「pop操作を行う＝要素を取り出す」なので、pop操作を行ったあとにはその要素はスタックに残っていません（当たり前ですが）。
まとめ
以上となります。間違いや改善点などございましたら、よろしくお願いいたします。