ホーム » スタッフ » 斉藤徹 » 2分木の応用(式の表現)

2004年11月
« 10月   12月 »
 123456
78910111213
14151617181920
21222324252627
282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

2分木の応用(式の表現)

2分木の応用として、式の表現の説明を行う。

その前に式を、2分木を使わない場合の扱いとして、 ポーランド記法(前置記法)、逆ポーランド記法(後置記法)を説明し、 括弧なしで演算の優先順位を表現できることを説明する。 また、逆ポーランド記法のデータは、スタックを用いると簡単な処理で 式の値を計算できることを説明し、式を機械語に変換する際に 便利であることを説明する。 説明のついでに、演算子には右結合演算子と左結合演算子があることも説明。

次に、2分木で実際に式の表現を行う場合を説明する。 説明用の構造体には、以下を用いた。 このデータ構造で、データ生成用補助関数を作り、 式の木構造データを作るまでを解説する。 次週は、この式データの値を求めるプログラムを説明する予定。

struct Exp {
int  type ; /* 0:数値, 1:演算子   */
int  val ;  /* 数値の場合の値     */
char op ;   /* 演算子の場合の記号(あえて1文字) */
struct Exp* left ;
struct Exp* right ;
} ;