ホーム » スタッフ » 斉藤徹 » 講義録 » 情報構造論 » 意志決定木と式を表す木

2017年10月
« 9月   11月 »
1234567
891011121314
15161718192021
22232425262728
293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

意志決定木と式を表す木

意志決定木

2分木の応用で最も単純な物として、意志決定木がある。

yes/no の答えを回答すると、最終的に「あなたの性格は✕✕です」と表示するようなヤツ。

struct Tree {
    char*        q_a ;
    struct Tree* yes ;
    struct Tree* no ;
} ;
               top
                  \
            あなたは勉強が好き?
              /yes     \no
    ものづくりは好き?    人と話すのが好き?
     /yes    \no      /yes    \no
技術者タイプ    ◯◯◯  営業タイプ  ◯◯◯


このような場合、プログラムは…

struct Tree* tcons( char*s, struct Tree*y, struct Tree*n )
{   struct Tree* ans ;
    ans = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
    if ( ans != NULL ) {
        ans->q_a = s ;
        ans->yes = y ;
        ans->no  = n ;
    }
    return ans ;
}
void main() {
    struct Tree* top =
        tcons( "あなたは勉強が好き?" ,
               tcons( "ものづくりは好き?" ,
                      tcons( "技術者タイプ , NULL , NULL ) ,
                      tcons( "...." , NULL , NULL ) ) ,
               tcons( "人と話すのが好き?" ,
                      tcons( "営業タイプ" , NULL , NULL ) ,
                      tcons( "...." , NULL , NULL ) ) ) ;
    struct Tree* p = top ;
    while( p->yes != NULL && p->no != NULL ) {
        char a[10] ;
        printf( "%s" , p->q_a ) ;
        scanf( "%s" , a ) ;
        if ( strcmp( a , "yes" ) == 0 )
            p = p->yes ;
        else
            p = p->no ;
    }
    printf( "%s¥n" , p->q_a ) ;
}

※ このプログラムの問題点は?

演算子と2分木

2分木の応用の例としては、式の表現などがある。

例えば、”1+2*3″という式があった場合、”(1+2)*3=9″なのか”1+(2*3)=7″なのか。(数学では演算子の優先順位から後者)、こういう演算子の優先順位をカッコで表さないためには、どうするか?

中置記法 1+2*3 = 1 + (2 * 3)   +
                             /  \
前置記法 +,1,*,2,3     1   *
                  / \
後置記法 1,2,3,*,+         2   3

後置記法は、コンピュータで計算をする場合に都合が良く、ポーランド記法としてよく知られている。

コンピュータで式を表すデータを、2分木に表現することもできる。こういった文法や処理を表す木は、構文木とも呼ばれる。

演算子では、演算子の優先順位以外にも、左結合・右結合といったものも重要となる。

左結合演算子 1+2+3+4 → ((1+2)+3)+4
右結合演算子 x=y=z=0 → x = (y = (z=0))