ポーランド記法(前置記法）のアルゴリズム

質問

ポーランド記法を使用した計算のアルゴリズムについて教えてください。

逆ポーランド記法についてはたくさんの資料が存在しますが、ポーランド記法については資料がないのでどのように考えたらよいのかわかりません。

スタック又は木構造を用いて計算するアルゴリズムをお願い致します。

回答No.1

dummyplug · ベストアンサー

学校の課題か何かですか？

正直、（RPNもそうですが）ポーランド記法でかかれた式の計算方法は資料をあたらないと考えつかないほどの難しさではないと思います。資料がないからといって諦めず、まずご自分で考えてみることが大切だと思います。その上でわからない（うまくいかない）ところを訊く方が勉強になるでしょう。

ざっと書くと
＜式の評価＞：
　step 1)1トークン読み出し
　step 2-1)トークンが値であれば、それが式の値
　step 2-2)トークンがオペレータ（関数）であれば、引数の数だけ続く式を評価してそれら評価値に対してオペレータを適用した結果が式の値
という感じです。これのどこに木構造やスタックを使うとよいかはやってみればわかります。わからなければとりあえずスタックなどなしでまず書いてみてから再度質問してみてください。

お礼

回答ありがとうございます。

具体的にわからない処は、
後置記法の場合は順々に計算していけばいいのでスタックのそのままの考え方で片付くものです。
しかし、前置になるとトークンを保持しておかなければいけないという点でどのように解決すればいいのかという疑問が生じています。

回答No.2

dummyplug

＞前置になるとトークンを保持しておかなければいけないという点でどのように解決すればいいのかという疑問が生じています。

了解です。こうして具体的に（ご自分で考えたなりの）疑問を投げてくれると解説しやすいです。
答えから言うと、その前置されたトークンの保持に（も）スタックを使います。

ANo.1で書いた方法は再帰的に処理をする（「式」の評価の中で「式」の評価を使っている）ようになっていることは理解できますか？
これをもちろん再帰的に呼び出すようにしてコーディングすることはできます。再帰は事実上のスタック使用ですからこれで「スタックを使った」と言ってしまうのも一つですけれど、ちょっとあんまりなので明示的にスタックを使ってみます。

一つの例として、制御構造は再帰を使い、値の保持にスタックを使ってみます。これだとANo.1と大して変わりません。step 2-2の部分で
step 2-2-1) オペレータの引数の個数をnとする
step 2-2-2) 「式を評価し、スタックに積む」をn回繰り返す
step 2-2-3) スタックトップからn個の値を取り出し、オペレータを適用する
こうしたとき、たとえば"* + 2 3 - 5 1"というPN式を評価するとどうスタックが使われるか理解できますか？（ただし、オペレータ"*","+","-"はそれぞれ引数2個を取るとします。）

先に「再帰でやっていることを明示的にスタックに」というようなことを書いたように、制御構造として使った再帰をやめてスタックを利用するような例を書いてみます。
この場合、制御構造としてはループを使います。再帰によって（実行）スタックに保持されていたオペレータの情報を明示的にスタックに保持するようにします。
スタックは上の例で書いた値を保持するスタックと共用することもできますが、複雑になって見通しが悪いので値スタックとは別にオペレータスタックを用意します。
step 0) 引数カウンタは1
step 1) 1トークン読みだし
step 2-1) トークンがオペレータでなければstep 3へ進む
step 2-2) 引数カウンタとオペレータをオペレータスタックに積む
step 2-3) オペレータの引数の個数を引数カウンタにセット
step 2-4) step 1に戻る
step 3) 値を値スタックに積む
step 4) 引数カウンタをデクリメント
step 5) 引数カウンタが0でなければstep 1に戻る
step 6) オペレータスタックが空ならおしまい
step 7) オペレータスタックからオペレータと引数カウンタを取り出す
step 8) オペレータの引数の数分だけ値スタックから取り出してオペレータを適用
step 9) 適用結果を値スタックに積んでstep 4に戻る
という感じです。あえて整理していませんのでこのままコーディングしようとするとかな～り嫌な感じ（構造化されていない）のコードになります。
何をやっているか理解できれば整理は難しくないと思うので、自分で試してみてください。（上と同じく"* + 2 3 - 5 1"というポーランド記法の式を計算するとどういう動きか追ってみるとよいでしょう。）

整理ができたなら、（興味があればですが）値スタックとオペレータスタックを共用するとどうなるか、とか、引数カウンタを使わないで済ますには、とか考えると色々なアイデアを導けると思います。

ところで、木構造を使う例についても少しふれておきます。でも詳しくは書きません。（興味があれば訊いてもらえれば書きますけど。）

処理の仕方の一例としては、元のポーランド記法のトークンをオペレータで区切りながら木構造を生成します。オペレータの引数の個数に応じてN進木になります。（2進木で構成することも当然できます。）表記としてたとえば3個の葉を持つ木を(a b c)というように表記するとしたら、"* + 2 3 - 5 1"というポーランド記法をパースして(* (+ 2 3) (- 5 1))という木を構成します。こうすると木のあるノードについて一番最初（左）の要素がオペレータ、それ以外の要素がオペレータに対する引数になっています。
こうなれば計算は簡単で、木をトラバースしながら引数にオペレータを適用していけば式の値を求めることができます。

こういう表記を見るとわかる人にはわかるかもしれませんが、ポーランド記法を使っている代表的な言語系にLISP系の言語があります。RPNな処理系に
FORTHとかPostscriptがあるのと似ています。
ですので、LISP処理系のパーサやevalなどを読むことでポーランド記法の処理を勉強することもできます。（それだけのために読むのはちょっと大げさかと思いますけど。）

お礼

回答ありがとうございます。
返答が遅れて申し訳ありません。
長文ありがとうございます。

スタックを利用した結果次のようにシミュレートできると考えました。

* + 2 3 - 5 1 である場合。

1.
オペレーター、引数スタック
*,2
値スタック
なし

2.
オペレーター、引数スタック
+,2
*,2
値スタック
なし

3.
オペレーター、引数スタック
+,2
*,2
値スタック
3
2

4.
オペレーター、引数スタック
+,2
*,3
値スタック
3
2
値スタックから（引数カウンタ2なので）2回Ｐｏｐして2+3を実行し、値スタックに積む。

5.
オペレーター、引数スタック
*,2
値スタック
5

6.
オペレーター、引数スタック
-,2
*,2
値スタック
5

6.
オペレーター、引数スタック
-,2
*,2
値スタック
1
5
5

7,
オペレーター、引数スタッフ
*,2
値スタック
4
5
値スタックから引数分だけＰＯＰしてオペレーターの適応。そして、値スタックに積む。

8,
オペレーター、引数スタッフ
*,2
値スタック
4
5

9,
オペレーター、引数スタッフ
なし
値スタック
20

答え20

というような流れだと認識致しました。
もし、お手数でなければ木構造についても教えていただければ幸いです。

よろしくお願い致します。