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

2015年12月

    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    

アーカイブ

Google

このブログ記事について

このページは、T-Saitohが2010年11月10日 12:17に書いたブログ記事です。

ひとつ前のブログ記事は「Moodleネットワーク機能」です。

次のブログ記事は「秋の遠足にてバーベキュー」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。