2分木の応用として式の表現の説明を行うけど、その前に計算式の一般論の説明を行う。
逆ポーランド記法
一般的に 1*2 + 3*4 と記載すると、数学的には演算子の優先順位を考慮して、(1*2)+(3*4) のように乗算を先に行う。このような優先順位を表現する時に、()を使わない方法として、逆ポーランド記法がある。
演算子の書き方には、前置記法、中置記法、後置記法があり、後置記法は、「2と3を掛ける、それに1を加える」と捉えると、日本語の処理と似ている。
中置記法 1+2*3 前置記法 +,1,*,2,3 後置記法 1,2,3,*,+ # 1と「2と3をかけた値」をたす。
後置記法は、一般的に逆ポーランド記法(Reverse Polish Notation)とも呼ばれ、式を機械語の命令に置き換える際に役立つ。
演算子の右結合・左結合
例えば、”1/2*3″という式が与えられたとする。この結果は、1/6だろうか？3/2だろうか？
一般的な数学では、優先順位が同じ演算子が並んだ場合、左側から計算を行う。つまり”1/2*3″は、”(1/2)*3″を意味する。こういった左側の優先順位が高い演算子は左結合の演算子という。
ただしC言語では、”a = b = c = 0″ と書くと、”a = (b = (c = 0))” として扱われる。こういった代入演算子は、 右結合の演算子である。
理解度確認
以下の式を指定された書き方で表現せよ。
逆ポーランド記法 1,2,*,3,4,*,+ を中置記法で表現せよ。 中置記法 (1+2)*3-4*5 を逆ポーランド記法で表現せよ。
以前の情報処理技術者試験では、スタックの概念の理解の例題として、逆ポーランド記法への変換アルゴリズムのプログラム作成が出題されることが多かったが、最近は出題されることはなくなってきた。
逆ポーランド記法の式の実行
この逆ポーランド記法で書かれた式から結果を求めるプログラムは以下のように記述できる。このプログラムでは式を簡単にするため、数値は1桁の数字のみとする。
// 単純な配列を用いたスタック
int stack[ 10 ] ;
int sp = 0 ;
void push( int x ) {
stack[ sp++ ] = x ;
}
int pop() {
return stack[ --sp ] ;
}
// 逆ポーランド記法の計算
int rpn( char* p ) {
for( ; *p != '// 単純な配列を用いたスタック
int stack[ 10 ] ;
int sp = 0 ;
void push( int x ) {
stack[ sp++ ] = x ;
}
int pop() {
return stack[ --sp ] ;
}
// 逆ポーランド記法の計算
int rpn( char* p ) {
for( ; *p != '\0' ; p++ ) {
if ( isdigit( *p ) ) {
// ~~(A)
// 数字はスタックに積む
push( *p - '0' ) ;
// ~~~~~~~~(B)
} else if ( *p == '+' ) {
// 演算子+は上部2つを取出し
int r = pop() ;
int l = pop() ;
// 加算結果をスタックに積む
push( l + r ) ;
} else if ( *p == '*' ) {
// 演算子*は上部2つを取出し
int r = pop() ;
int l = pop() ;
// 乗算結果をスタックに積む
push( l * r ) ;
}//~~~~~~~~~~~~~(C)
}
// 最終結果がスタックに残る
return pop() ;
}
void main() {
printf( "%d\n" , rpn( "123*+" ) ) ;
}
' ; p++ ) {
if ( isdigit( *p ) ) {
// ~~(A)
// 数字はスタックに積む
push( *p - '0' ) ;
// ~~~~~~~~(B)
} else if ( *p == '+' ) {
// 演算子+は上部2つを取出し
int r = pop() ;
int l = pop() ;
// 加算結果をスタックに積む
push( l + r ) ;
} else if ( *p == '*' ) {
// 演算子*は上部2つを取出し
int r = pop() ;
int l = pop() ;
// 乗算結果をスタックに積む
push( l * r ) ;
}//~~~~~~~~~~~~~(C)
}
// 最終結果がスタックに残る
return pop() ;
}
void main() {
printf( "%d\n" , rpn( "123*+" ) ) ;
}
逆ポーランド記法の式の実行は、上記のようにスタックを用いると簡単にできる。このようなスタックと簡単な命令で複雑な処理を行う方法はスタックマシンと呼ばれる。Java のバイトコードインタプリタもこのようなスタックマシンである。
Cプログラママニア向けの考察
上記のプログラムでは、int r=pop();…push(l+r); で記載しているが、
push( pop() + pop() ) ;とは移植性を考慮して書かなかった。理由を述べよ。
最初の関数電卓
初期の関数電卓では複雑な数式を計算する際に、演算子の優先順位を扱うのが困難であった。このため、HP社の関数電卓では、式の入力が RPN を用いていた。(HP-10Cシリーズ)
2項演算と構文木
演算子を含む式が与えられたとして、古いコンパイラではそれを逆ポーランド変換して計算命令を生成していた。しかし最近の複雑な言語では、計算式や命令を処理する場合、その式(または文)の構造を表す2分木(構文木)を生成する。。
＋ ／ ＼ １ ＊ ／ ＼ ２ ３
演算子の木のノードで、末端は数値であることに注目し、右枝・左枝がNULLなら数値(data部にはその数値)、それ以外は演算子(data部には演算子の文字コード)として扱うとして、上記の構文木のデータを作る処理と、その構文木の値を計算するプログラムを示す。
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 ) { // ~~~~~~~~~~~~~~~~~~~~~(D)
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 ) ;
} // ~~~~~~~~~~~~~~~(E) ~~~~~~~~(F)
}
}
void main() {
struct Tree* exp = // 1+(2*3) の構文木を生成
tree_op( '+' ,
tree_int( 1 ) ,
tree_op( '*' ,
tree_int( 2 ) ,
tree_int( 3 ) ) ) ;
printf( "%d¥n" , eval( exp ) ) ;
}
理解度確認
- push(),pop() のスタックは、保存と取り出しの順序を表す単語の頭文字4つを使って何と呼ばれるか？
- 上記プログラム中の(A)～(F)の型を答えよ。