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

2005年11月
« 10月   12月 »
 12345
6789101112
13141516171819
20212223242526
27282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

式の表現(2分木)

2分木を使った式の表現の説明。

2分木を使わない場合

式といっても、演算子の優先順位や結合方向などの問題がある事を説明した後、 逆ポーランド記法などがあることを説明し、 逆ポーランド記法のなら、値を計算する事はスタックを使えば簡単であることを説明。

2分木を使った式の表現

今までの知識だけで2分木を使って式を表現すると、 木の枝のポインタは『値』の場合と『木』の場合があるので、どうするか? といった話題から、木を表現するデータ構造の宣言を考えさせる。

struct Exp {
int  type ;         /* 節が数値か演算子か? */
char op ;           /* 数値の場合 */
int  value ;        /* 値の場合 */
struct Exp* left ;  /* 左右の枝 */
struct Exp* right ;
} ;

このデータ構造の場合の『無駄』をどう対処すべきかを答えてもらう。 授業で提案された方式は、以下の3つであった。
# 案1,案3を組み合わせて、共用体を使ったデータ構造の宣言例を示す。
# あわせてtypeのbit数を減らすために、ビットフィールドを使う場合もあることを紹介

  1. op と value は同時に使わないから、 value に演算子コードを保存すれば op は不要!
  2. 数値の場合には、op に数値を表すコードを割り当てれば、type は不要!
  3. 数値の場合は left , right も NULL なので、type は不要!

最後に、上記データ構造での、式の値を求める eval を説明する。