ホーム » 2006 » 11月 » 07

日別アーカイブ: 2006年11月7日

2006年11月
« 10月   12月 »
 1234
567891011
12131415161718
19202122232425
2627282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

2分木と演算子データの扱い

2分木構造の応用のネタとして、2項演算子による式の表現を2分木を用いて行う方法を説明。

式の表現方法

式の表現方法として、中置記法、前置記法 (ポーランド記法) ) FN ポーランド記法の由来は、提唱者がポーランド人だかららしい。 /FN 、後置記法 (逆ポーランド記法) 特に、逆ポーランド記法等は、書き方自体が演算子の優先順位を含んでいる点や、 コンパイラを作成する時などの機械語生成が容易、スタックで実装が容易といった点を説明する。 逆ポーランド変換も基本情報処理の問題として定番なので、説明したいけど時間がかかるし データ構造とは離れるので、紹介のみ。 式の優先順位や右結合・左結合といった用語も説明する。

2分木で式を表現

最後に2分木で式を表現・生成し、 その値を実際に再帰呼び出しで値を計算するプログラム例を説明する。

struct Expr {
int          data ;   // 数値データの場合は、left=right=NULLとする。
struct Expr* left ;
struct Expr* right ;
} ;
// 数値の木を生成
struct Expr* Integer( int x )
{   struct Expr* ne ;
ne = (struct Expr*)malloc( sizeof( struct Expr ) ) ;
if ( ne != NULL ) {
ne->data = x ;
ne->left = ne->right = NULL ;
}
return NULL ;
}
// 演算子の木を生成
struct Expr* Operator( char op , struct Expr* l , struct Expr* r )
{   struct Expr* ne ;
ne = (struct Expr*)malloc( sizeof( struct Expr ) ) ;
if ( ne != NULL ) {
ne->data  = op ;
ne->left  = l ;
ne->right = r ;
}
return NULL ;
}
// 木のデータを式として評価する
int eval( struct Expr* e ) {
if ( e->left == NULL && e->right == NULL ) {
return e->data ;
} else {
switch( e->data ) {
case '+' : return eval( e->left ) + eval( e->right ) ;
case '*' : return eval( e->left ) * eval( e->right ) ;
}
}
}
// 動作確認
void main() {
// e = 1 + 2 * 3 ;
struct Expr* e = Operator( '+' , Integer( 1 ) ,
Operator( '*' , Integer( 2 ) ,
Integer( 3 ) ) ) ;
printf( "%d\n" , eval( e ) ) ;
}

説明の途中で、余りにも雷雨が激しいので、雑談として落雷や感電の説明をする。 んで、真面目な授業のネタよりも、こういう雑談の方が学生さんはよく覚えているのが、 現実だったりする。 (人間の体内は手足間で平均500Ω程)

トラックバック SPAM が大量に…

気づくとトラックバック SPAM が大量に書き込まれていた。 対応も面倒だし、トラックバック機能を止める。

おもしろいアイディアだけど…

おもしろいアイディアだけど…

広告アイディアを、製品販売元とは関係なしにユーザが提案して、 広告を企業に『押し売り』しようという、ユニークなビジネスモデル。

だけど…

だけど、広告サンプルなのか本気なのかちょっと解らないけど、 物は???である。

  • 007:背が伸びるつり革:身長の低い人向けの電車のつり革に、 専用の広告を…というアイディアなんだけど、 ある意味… 『チビにけんか売る気かぁ〜?』 というアイデアである。
  • 006:このブツブツが目に入らぬか:盲人向けの道路の点字ブロックを ベネトンカラーのように配色し、広告ネタにしようというアイデア… だけど点字ブロックは、弱視の人が『黄色』で目立つ目印としても 利用していて、黄色以外だと視認性が落ちるという視点が抜けているんだなぁ…

ということで『押し売り』の名前通り、 相手にとっての視点が『びっみょ〜♪』に配慮に欠けている、変なサイトだったとさ。