前置記法と二分木リスト

前置記法の作成手順をまとめるとともに、前置記法と二分木リストとの間の関係について述べました。またそこから発想を得た以前とは異なる中置記法から二分木リストを作成する方法を紹介します。





前置記法

 今回は「数式と二分木リスト」と「いまさらですが逆ポーランド記法への変換」の続きです。これらの記事では触れなかった前置記法への変換についてまとめ、並びに以前紹介したのとは異なる二分木リストへの変換方法について述べます。

 前置記法では、1 + 2 が、+ 1 2 のように演算子が先頭に来て、それに続いてオペランド(演算子から操作されるもの)が続くという数式表記方でポーランド記法とも、呼ばれます。この記法も、以下で述べるように式の計算をプログラムするのに都合の良い方法ですが、その点に関しては逆ポーランド記法の方が、すっきりしたアルゴリズムになるので優位性は感じられません。ただこの形式では演算子を引数を二つとる関数とみなすことが可能で、LISPなどの言語ではこれを利用しています。

作成の手順

 最初に、中置記法(通常の式表記法)から前置記法を作る手順を示します。ここで紹介する方法は式を後ろから読んでいますが、前から式を読んで変換することも可能です。ただし、その方法は手順がごちゃごちゃしていたので、手順がすっきりする後ろから読む方法を紹介することにしました。添付した図「中置記法から前置記法に変換」で具体的な例での変換を示したので、そちらも参考にしてください。変換手順は以下の通りです。

1.式を構成要素(数値、演算子、関数、括弧など)に分解する。
 以下ではこの分解要素を後ろから読んでいく。(例えば1 + 2 なら2、+ 、1 の順で読む)

2.演算子を積むスタックを用意する。

3.数字を読んだらそのまま出力する。すでに出力中の式文の前に追加する。

4.演算子(A)を読んだ時スタック中に演算子(B)があるなら、それを上(新しく積んだものが上)から
取り出し優先度を比較する。
 Aの優先度がBより高いか等しければ演算子Aをスタックに積む。
 そうでないならBを取り出し出力する(出力文の前に追加)。
 これをAの優先度がスタック中の演算子の優先度より高いか等しくなるまで繰り返す。

 最後にAをスタックに積む。

5.括弧で囲まれている部分は、その内部を取り出して処理しその結果を出力文の前に追加する。
 関数の場合は括弧内処理出力文の前に関数名を追加
(例 sin(1+2) なら sin( + 1 2 この例ではsinの後に括弧をつけてこれが関数であることを示しています )

6.式要素を一番前まで読み終わった時、スタックに残っている演算子を一番上から取り出して
出力文の前に追加してゆく。

前置記法での計算手順

 次に前置記法を使って式の計算を行う手順を考えます。以下の手順も式(今度は前置記法の式ですが)を、最後から前に読んでいきます。添付した図「前置記法の式の計算」で具体例を使って説明しているので、そちらもご覧ください。式の値を計算する手順は以下の通りです。

1.計算結果と数値を積むスタックを用意する。

2.式要素を後ろから読んでゆく。数値はスタックに積む。

3.演算子opが出たらスタックの一番上の値A、一つ下の値Bを取り出してA op B を計算する。
 ( op が + なら A + B を計算するといった具合 )
 計算結果をB が入っていたスタックに入力する。一番上は空にする。

4. 2 と3 の操作を式要素を全部読み終わるまで繰り返す。

5.スタックに計算結果が残る。

前置記法と二分木リストの関係

前置記法から二分木リスト作成の手順

 さて次は、前置記法から二分木リストを作成する方法です。後置記法の時と同じく、これは式の値を計算する時の手順を少し変更することで可能です。上記の手順で以下の点を変更します。

 まずA op B で計算を実行している部分を、演算子オブジェクトopの左フィールドにAの参照、右フィールドにBの参照を代入する操作に変更し、スタックに計算結果の代わりに、この演算子オブジェクトを積みます。この操作の結果、式を最後まで読み終わるとスタックにはルートオブジェクトが残ります。なお二分木リストならびに左フィールド、右フィールド等については、「数式と二分木リスト」で」説明しています。

二分木リストの表記方法について

 ところで二分木リストを表すのに、付属図の「二分木リストと前置記法」で示したような書き方をしたとします。(オブジェクトopが、あってその左フィールドが指すオブジェクトがA ,右フィールドが指すオブジェクトがBという場合、op(A ,B)と表す。)するとこの付図に示した例の通り、この表現での二分木リストは前置記法そのものになります。

 この事から中置記法を前置記法に変換する方法を、すこしいじれば「数式と二分木リスト」で紹介したのと異なる方法で中置記法から二分木リストを作成する方法が見つかるのではないかと考えました。

 以前紹介した方法では最初に式を最後まで読む必要があり、前から順々に読む方法はないものか考えました。以下で示す方法は、括弧や関数引数部分はまとめて処理する必要があるものの基本的には前から順に読んでいけば二分木リストが作成できるようになっています。なお最初は前置記法への変換を基に手順を考えたのですが、やはり式を逆向きに読む方法になってしまったので、後置記法への変換を基に考えたのが以下で紹介している手順です。

二分木リスト作成 別の手順

 付属の図「中置記法から二分木リストを作成する方法2」と「(続き)」で具体的な例を使って説明しているのでご覧ください。

1.数値と左・右フィールドを与えたオブジェクトを保管するスタックAと演算子を積むスタックBを用意する。

2.式の要素を最初から読んでいき数値が出たらAに積んでいく。

3.演算子(α)を読んだら、スタックBで一番上にある演算子(β)を取り出しαと優先度を比較する。
 αの優先度の方が小さいか同じならβを取り出しAの一番上のオブジェクa1への参照をβの右フィールドに、
上から二番目のオブジェクa2への参照を左フィールドに入れて、βをスタックAの上から二番目(a2が入っていたところ)に
入れる。一番上は空にする。
 これをαの優先度の方が大きくなるまで続ける。その後αをスタックBに積む。

4.式を最後まで読んだら、スタックBに残っている演算子の左右フィールドにスタックAの上から二番目、一番目の
オブジェクへの参照を代入する。
 この演算子がルートオブジェクトになる。

5.括弧で囲まれた部分と関数の引数部分は、取り出してその中に上記の処理を行う。

 以上で中置記法から二分木リストを作成する事が可能です。

Additional Images




Comments

Loading…

We use cookies and other technologies to improve your experience on our website and to analyze our traffic. By browsing our website, you consent to our use of cookies and other tracking technologies.

Accept cookies and close this message