2分木構造の応用のネタとして、２項演算子による式の表現を２分木を用いて行う方法を説明。

式の表現方法

式の表現方法として、中置記法、前置記法 (ポーランド記法) ) FN ポーランド記法の由来は、提唱者がポーランド人だかららしい。 /FN 、後置記法 (逆ポーランド記法) 特に、逆ポーランド記法等は、書き方自体が演算子の優先順位を含んでいる点や、 コンパイラを作成する時などの機械語生成が容易、スタックで実装が容易といった点を説明する。 逆ポーランド変換も基本情報処理の問題として定番なので、説明したいけど時間がかかるし データ構造とは離れるので、紹介のみ。 式の優先順位や右結合・左結合といった用語も説明する。

２分木で式を表現

最後に2分木で式を表現・生成し、 その値を実際に再帰呼び出しで値を計算するプログラム例を説明する。

struct Expr {
int          data ;   // 数値データの場合は、left=right=NULLとする。
struct Expr* left ;
struct Expr* right ;
} ;
// 数値の木を生成
struct Expr* Integer( int x )
{   struct Expr* ne ;
ne = (struct Expr*)malloc( sizeof( struct Expr ) ) ;
if ( ne != NULL ) {
ne->data = x ;
ne->left = ne->right = NULL ;
}
return NULL ;
}
// 演算子の木を生成
struct Expr* Operator( char op , struct Expr* l , struct Expr* r )
{   struct Expr* ne ;
ne = (struct Expr*)malloc( sizeof( struct Expr ) ) ;
if ( ne != NULL ) {
ne->data  = op ;
ne->left  = l ;
ne->right = r ;
}
return NULL ;
}
// 木のデータを式として評価する
int eval( struct Expr* e ) {
if ( e->left == NULL && e->right == NULL ) {
return e->data ;
} else {
switch( e->data ) {
case '+' : return eval( e->left ) + eval( e->right ) ;
case '*' : return eval( e->left ) * eval( e->right ) ;
}
}
}
// 動作確認
void main() {
// e = 1 + 2 * 3 ;
struct Expr* e = Operator( '+' , Integer( 1 ) ,
Operator( '*' , Integer( 2 ) ,
Integer( 3 ) ) ) ;
printf( "%d\n" , eval( e ) ) ;
}

雷

説明の途中で、余りにも雷雨が激しいので、雑談として落雷や感電の説明をする。 んで、真面目な授業のネタよりも、こういう雑談の方が学生さんはよく覚えているのが、 現実だったりする。 (人間の体内は手足間で平均500Ω程)