2分木の応用として、式の表現の説明を行う。
その前に式を、2分木を使わない場合の扱いとして、 ポーランド記法(前置記法)、逆ポーランド記法(後置記法)を説明し、 括弧なしで演算の優先順位を表現できることを説明する。 また、逆ポーランド記法のデータは、スタックを用いると簡単な処理で 式の値を計算できることを説明し、式を機械語に変換する際に 便利であることを説明する。 説明のついでに、演算子には右結合演算子と左結合演算子があることも説明。
次に、2分木で実際に式の表現を行う場合を説明する。 説明用の構造体には、以下を用いた。 このデータ構造で、データ生成用補助関数を作り、 式の木構造データを作るまでを解説する。 次週は、この式データの値を求めるプログラムを説明する予定。
struct Exp { int type ; /* 0:数値, 1:演算子 */ int val ; /* 数値の場合の値 */ char op ; /* 演算子の場合の記号(あえて1文字) */ struct Exp* left ; struct Exp* right ; } ;