今日は、2分木を用いた式の表現とB木について説明を行う。 前回、２項演算子の話で、逆ポーランド記法などの説明をしたので、 そのプログラム例から話を行う。

逆ポーランド記法のスタック処理

逆ポーランド記法による式は、スタックを用いると簡単にその値を求める処理が記述できる。

// スタックの記述
int stack[ 10 ] ;
int *sp = stack ;
void push( int x ) {
*sp++ = x ;
}
int pop() {
return *--sp ;
}
// 逆ポーランド記法の式を処理する関数
int eval( char* s ) {
for( ; *s != '
// スタックの記述
int stack[ 10 ] ;
int *sp = stack ;
void push( int x ) {
*sp++ = x ;
}
int pop() {
return *--sp ;
}
// 逆ポーランド記法の式を処理する関数
int eval( char* s ) {
for( ; *s != '\0' ; s++ ) {
if ( *s >= '0' && *s <= '9' ) {
push( *s - '0' ) ;
} else {
switch( *s ) {
case '+' : push( pop() + pop() ) ; break ;
case '*' : push( pop() * pop() ) ; break ;
}
}
}
return pop() ;
}
void main() {
printf( "%d\n" , eval( "12+3*" ) ) ;
}
' ; s++ ) {
if ( *s >= '0' && *s <= '9' ) {
push( *s - '0' ) ;
} else {
switch( *s ) {
case '+' : push( pop() + pop() ) ; break ;
case '*' : push( pop() * pop() ) ; break ;
}
}
}
return pop() ;
}
void main() {
printf( "%d\n" , eval( "12+3*" ) ) ;
}

2分木による式の表現

これが本来説明したい2分木による式の表現。 データ構造を簡単にしたいので、 左右の枝がNULLなら、opr部に整数値、非NULLなら、opr部に演算子の文字コードとする。 この方式であれば、要素名は異なるものの、２分木のデータ宣言とまるっきり同じ。

// まずはデータ構造の宣言と、そのデータを生成する補助関数。
struct Expr {
int opr ;
struct Expr* left ;
struct Expr* right ;
} ;
// 数値の場合
struct Expr* Integer( int x ) {
struct Expr* ans ;
ans = (struct Expr*)malloc( sizeof( struct Expr ) ) ;
if ( ans != NULL ) {
ans->opr = x ;
ans->left = NULL ;
ans->right = NULL ;
}
return ans ;
}
// 演算子の場合
struct Expr* Operator( int op ,
struct Expr* l ,
struct Expr* r ) {
struct Expr* ans ;
ans = (struct Expr*)malloc( sizeof( struct Expr ) ) ;
if ( ans != NULL ) {
ans->opr = op ;
ans->left = l ;
ans->right = r ;
}
return ans ;
}

データ構造を作る処理が記述できたところで、その式の表示と、その式の計算。

// 2分木による式を表示する関数。
// 演算子の優先順位を無視して、全てにカッコをつける
void print_expr( struct Expr* e ) {
if ( e->left == NULL && e->right == NULL ) {
printf( "%d" , e->opr ) ;
} else {
printf( "(" ) ;
print_expr( e->left ) ;
printf( "%c" , e->opr ) ;
print_expr( e->right ) ;
printf( ")" ) ;
}
}
// 式の値を計算する関数
int eval_expr( struct Expr* e ) {
if ( e->left == NULL && e->right == NULL ) {
return e->opr ;
} else {
switch( e->opr ) {
case '+' :
return eval_expr( e->left )
+ eval_expr( e->right ) ;
case '*' :
return eval_expr( e->left )
* eval_expr( e->right ) ;
}
}
}
// 実際に計算させてみる。
void main() {
struct Expr* e
= Operator( '*' ,
Integer( 1 ) ,
Operator( '+' ,
Integer( 2 ) ,
Integer( 3 ) ) ) ;
printf( "%d\n" , eval_expr( e ) ) ;
}

B木

2分木で式の表現を説明したが、枝の数は左右２本と限定する必要はあるのだろうか？ 2本をN本に拡張したものが、B木と呼ばれる。

// 位数2のBTree
struct BTree {
int size ; // B木のノード内のデータ数
int d[ 4 ] ; // 実際のデータ
struct BTree* p[ 5 ] ; // d[i] < ● < d[i+1] のデータは、
// p[i+1]の枝に保存
} ;

B木では、枝に関する条件に加え、位数Nの場合では、ノード内のデータ件数を必ず、 N <= (データ件数) <=2N を満たすようにする。

データの追加で、ノード内のデータ件数が2Nを越える場合には、 加えるデータを含め、データ順に並べた時の中央値を上位ノードに移動させ、 ノードを、左右に分割を行う。

|
　　[ 12 | 21 | 23 | 29 ]  ← 18を加えるなら、12,18,21,23,29 で、
　　　　　　　　　　　　　　　　　21を上位に上げる。
[ 8 |(21)| 39 | × ]
|    |
|    +---------------+
|                    |
[ 12 | 18 | × | × ]  [ 23 | 29 | × | × ]

先週の2分木の演習に引き続き、後半を演習とした。

前半では、プログラミングへの興味を持って欲しいし、 先週のプロコンの状況を紹介した。

課題部門での作品の背景として、FireChat というソフトがあり、 香港の学生デモでも活躍していたことを話す。 また、情報統制でインターネットでどういうことが発生するかということで、 FireWallによる制限や、DNS 統制などの雑談も行った。

演算子の話

2分木の応用で、式の取扱いを来週解説する予定なので、 演算子の一般的な知識を説明。

なにげない「1+2*3」という式も、演算子には優先順位があり、 「1+(2*3)」を意味している。この優先順位を()で表さないためにはどうすればいいのか？

C言語で使われている演算子も細かく分類すると、 単項演算子、2項演算子、3項演算子(条?真値:偽値)がある。 単項演算子も単純な「-(マイナス)、!(NOT)」という前置型の他に、 「++x , x–」といった前置・後置で処理が異なるものもある。 2項演算子も、「1+2+3」は「(1+2)+3」のように処理される左結合演算子と、 「x=y=0」が「x=(y=0)」として処理される右結合演算子があることを説明。

演算子の表記法にも、「1+2*3」を、「1,2,3,*,+」のように、 演算子の前に式を置く、後置記法(逆ポーランド記法)という方式もある。 逆ポーランド記法は、日本語の文法に近いということもあげられるが、 スタックを使い、『数値はスタックに詰む、演算子がでたらスタック上位の 2つの値を取り出し、計算結果を改めてスタックに詰む。』という処理を 繰り返せば、複雑な計算式も正しく値を求めることができる….といった説明を 行う。

ちなみに、「+,1,*,2,3」のような演算子を前に置くものは、前置記法(ポーランド記法)、「1+2*3」のような書き方は、中置記法と呼ぶ。

最初は「水泳は高専の授業科目に必要である…」

仕事で使っている、MacBookAir だけど、2010年の機種で、 そろそろ悩みどころ。 でも、ちょっとしたネット仕事であれば十分な性能だし、 議事録メモにEvernote中心であれば、それなりに使えている。 といっても、HDD の容量不足で不要ファイルをケチ臭く消したりと、 HDD交換すれば、まだまだ使えるかと考えていた。

その中で、Facebookの記事で見つけた、Transcend の SSD の JetDrive 500 を使えば、交換のためのドライバや、装換した後のSSDを入れるケース などが入っていて、交換作業も簡単そうなので、購入してみた。

JetDriveのアルミケースに入っていた240GB-SSDを一旦収納させ、 MacBookAirにUSB接続。 復旧モードで立ち上げて、元々の64GB-SSD の中身を全コピー。 附属の特殊ドライバーを使って MacBookAir の裏蓋を剥がして、 240GB-SSD に入替えて、交換完了。

自分で入替えだから、初心者には薦められないけど、思ったより 簡単な作業でした。