逆ポーランド記法による計算モデル

全文

(1)

算法の設計と解析  回目

逆ポーランド記法による計算モデル

中間表記

前置表記

後置表記

前置法はポーランド記法と呼ばれ,後置法は逆ポーランド記法と呼ばれる.

中置法 を前置法 に変換するには,図 のように木のトラーバースによる方法がある.

また, ×のときは,図のように × に変形する.ここで,中置法で用いられる が前 置法では必要ないことがわかる.これは,後置法でも同じである.

+

a b

+

a b

˜

c

トラバース

ここで,後置法は × × となる.これを見てわかるように,前から計算していくと,単純に計 算するできることがわかる.後置法のアルゴリズムをスタックを用いて,紹介する. はデータの入力,

はデータの出力である.

式の文字列から順にデータを読み込み,データが数値のとき, する.また,データが演算子のとき,スタッ クからし,計算結果を する.この作業を繰り返し,式の文字列全てを読み込んだとき,最後にス タックされているデータが計算結果となる.

(2)

後置法表記× を上記のアルゴリズムにしたがって,解いてみる.

読み込み 現在のスタック状況

数値の読み込み

数値の読み込み 演算子の読み込み

数値の読み込み

演算子 × の読み込み

× 終了

このように,計算結果と正しく求まります.

Updating...

参照

Updating...

関連した話題 :