2分木の応用(構文木と決定木)

今日は、2分木の応用ということで、2項演算子の構文木と、意思決定木の説明を行う。

時間があまったので、対話システムの雑談から、eliza の話をして、 本当は人工無能「うずら」ちゃんの話をしようと思っていたけど、 チューリングテストの話になって、 アラン・チューリングの話になって、 映画イミテーションゲームの説明をして、 2045年問題の話をして….どんどん暗い話題に…

2項演算と構文木

先週の講義で、演算子の話をしておいたので、演算式の2分木で扱うプログラムを説明。

　　　＋
　　／　＼
　１　　　＊
　　　　／　＼
　　　２　　　３

１つのノードは、演算子か末端の数値であることに注目し、 右枝・左枝がNULLなら数値、それ以外は演算子として扱うとして…

struct Tree {
   int  data ;
   struct Tree* left ;
   struct Tree* right ;
} ;
struct Tree* tree_int( int x )
{
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->data = x ;
      n->left = n->right = NULL ;
   }
   return n ;
}
struct Tree* tree_op( int op ,
         struct Tree* l , struct Tree* r ) {
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->data = op ;
      n->left = l ;
      n->right = r ;
   }
   return n ;
}
int eval( struct Tree* p ) {
   if ( p->left == NULL && p->right == NULL )
      return p->data ;
   else
      switch( p->data ) {
      case '+' : return eval( p->left ) + eval( p->right ) ;
      case '*' : return eval( p->left ) * eval( p->right ) ;
      }
}

void main() {
   struct Tree* exp =
      tree_op( '+' ,
               tree_int( 1 ) ,
               tree_op( '*' ,
                        tree_int( 2 ) , tree_int( 3 ) ) ) ;
   printf( "%d¥n" , eval( exp ) ) ;
}

関連する雑談として、プログラム言語の構文木の説明を行い、 (1) 字句解析 , (2) 構文解析 を組み合わせて作るけど、 字句解析支援ソフト(lex)や構文解析支援ソフト(yacc)などの紹介も行う。

意思決定木

意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。

((意思決定木の例:うちの子供が発熱した時))
　　　　　　　38.5℃以上の発熱がある？
　　　　　　no／　　　　　　　　　＼yes
　　　元気がある？　　　　　　　　むねがひいひい？
　yes／　　　　＼no　　　　　　no／　　　　　＼yes
様子をみる　氷枕で病院　　解熱剤で病院　　速攻で病院

struct Tree {
   char *qa ;
   struct Tree* yes ;
   struct Tree* no ;
} ;
struct Tree* dtree( char *s , struct Tree* l , struct Tree* r )
{  struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->qa = s ;
      n->yes = l ;
      n->no = r ;
   }
   return n ;
}
void main() {
   struct Tree* p =
      dtree( "38.5℃以上の発熱がある?" ,
             dtree( "胸がひぃひぃ" ,
                    dtree( "速攻で病院" , NULL , NULL ) ,
                    dtree( "解熱剤で病院" , NULL , NULL ) ) ,
             dtree( "元気がある?" ,
                    dtree( "様子をみる" , NULL , NULL ) ,
                    dtree( "氷枕で病院" , NULL , NULL ) ) ) ;
   struct Tree* d = p ;
   while( d->yes != NULL || d->no != NULL ) {
      printf( "%s¥n" , d->qa ) ;
      scant( "%d" , &ans ) ;
      if ( ans == 1 )
         d = d->yes ;
      else if ( ans == 0 )
         d = d->no ;
   }
   printf( "%s¥n" , d->qa ) ;
}