ホーム » スタッフ » 斉藤徹 » 2分木で式を表現

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

最近の投稿(電子情報)

アーカイブ

カテゴリー

2分木で式を表現

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

式と表記法

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

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

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

| | | | |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 ) ) ;
}