2分木の応用として、2項演算子と数値を表現する方法を説明した。

式と表記法

木での表現の前に、式を演算子の優先順位のカッコ無しで表現する手法として、 逆ポーランド記法などを説明する。また、逆ポーランド記法で表記されたデータを 処理する場合にはスタックなどが便利であることも説明する。

中置記法: 1+2*3
逆ポーランド記法: 1,2,3,*,+  (後置記法)
前置記法: +,1,*,2,3

スタックを使えば、逆ポーランド記法データから値を求める処理が簡単。 数値ならスタックに積む。演算子なら２つデータを取って計算し、結果を再びスタックに積む。

| | | | |3|               +
| | |2| |2| |6|         ／ ＼
|1| |1| |1| |1| |7|    1     *
-------------------        ／ ＼
1 , 2 , 3 , * , +        2     3

2分木で式を表現

struct Expr {
int          value ; // left,right==NULLの時は数値
char         op ;
struct Expr* left ;
struct Expr* right ;
} ;
struct Expr* Integer( int v ) { // 数値の木を作る
struct Expr* ans ;
ans = (struct Expr*)malloc( sizeof( struct Expr ) ) ;
if ( ans != NULL ) {
ans->value = v ;
ans->op    = ' ' ; // dummy
ans->left  = ans->right = NULL ;
}
return ans ;
}
struct Expr* Operator( char op , // 式の木を作る
struct Expr* l , struct Expr* r ) {
struct Expr* ans ;
ans = (struct Expr*)malloc( sizeof( struct Expr ) ) ;
if ( ans != NULL ) {
ans->value = 0 ; // dummy
ans->op    = op ;
ans->left  = l ;
ans->right = r ;
}
return ans ;
}
int eval( struct Expr* e ) { // 木の式を評価
if ( e->left == NULL && e->right == NULL ) {
return e->value ;
} else {
int l = eval( e->left ) ;
int r = eval( e->right ) ;
switch( e->op ) {
case '+' : return l + r ;
case '*' : return l * r ;
}
}
}
void main() {
struct Expr* exp =
Operator( '+' ,
Integer( 1 ) ,
Operator( '*' ,
Integer( 2 ) ,
Integer( 3 ) ) ) ;
printf( "%d" , eval( exp ) ) ;
}