第50回 プログラミングについて『ポーランド記法って知ってる？』
ポーランド記法という言葉を聞いたことがありますか？ そうですポーランドの人たちは皆この記法で言葉を書くのです... ではなく、数式の表現の１つでポーランドの人が考え出した数式の記述方法なのでこのような名前になっているのです。
このポーランド記法なる数式の記述方法は数値と演算子の優先順位を意識しないで計算ができるという記述方法なのです。一般的には逆ポーランド記法といって、数値を先に書き、演算子を後にする方法が使用されています。話だけではポーランド記法というものはどのようなものなのかが分からないと思いますので、例を紹介しましょう。（表現を簡単にするために数値は１桁とします。）
（１） 12+
（２） 123*+
（３） 12+34+*
初めて見る方には不思議な表現方法に見えると思いますが、（１）は 1+2 （２）は1+2*3 （３）は (1+2)*(3+4) を意味しています。
上の例をもう少し詳しく説明すると、
（１）は、1 と 2 を加算する。
（２）は、2 と 3 を乗算した結果に 1 を加算する。
（３）は、1 と 2 を加算した結果に 3 と 4 の加算した結果を乗算する。
と読めば分かりやすいと思います。要するに左から見ていき、最初の演算子の左側の２つの数値を演算し、その結果を演算子と２つの数値と置き換え、次の演算子を見ることを繰り返します。最後に残った数値が答えとなる訳です。
ここまでを理解するのが結構面倒でパズルを解いているようなのですが、理解してしまえば「なーるほど」と感心させられます。
さてこのポーランド記法ですが、筆算をするのに通常の数式の表現をわざわざこの記法に直してから計算をする人はいないと思います。そんなことをする暇があったらとっとと計算をした方が速いに違いありません。ということは多分、計算機で数式を処理するときに応用するのだろうということは想像がつくかと思います。
それでは実際に計算機の動きに合わせて上の例を考えてみましょう。
（１）の 12+ は、
1 をスタックにプッシュ。
2 をスタックにプッシュ。
+ はスタックから２つの値をポップして加算し、その結果をスタックにプッシュ。
（２）の 123*+ は、
1 をスタックにプッシュ。
2 をスタックにプッシュ。
3 をスタックにプッシュ。
* はスタックから２つの値をポップして乗算し、その結果をスタックにプッシュ。
+ はスタックから２つの値をポップして加算し、その結果をスタックにプッシュ。
（３）の 12+34+* は
1 をスタックにプッシュ。
2 をスタックにプッシュ。
+ はスタックから２つの値をポップして加算し、その結果をスタックにプッシュ。
3 をスタックにプッシュ。
4 をスタックにプッシュ。
+ はスタックから２つの値をポップして加算し、その結果をスタックにプッシュ。
+ はスタックから２つの値をポップして加算し、その結果をスタックにプッシュ。
ということになります。最後にスタックに残っている値が式の結果になります。
スタックという言葉が出てきました。そもそもは『積む』という意味です。プッシュするというのは積み上げることで、ポップするというのはそこから取り出すことです。これだけではイメージが浮かばないと思いますので、食器棚を考えて下さい。食器棚に皿を積み上げることがすなわちプッシュになり、その一番上の皿を取り出すことをポップということになる訳です。ですから最後にプッシュしたものが最初にポップされることは理解できると思います。
これでは普通の数式をどのようにしてこの逆ポーランド記法にすればいいのでしょうか。次の数式で考えてみましょう。
1+2*3
基本は数式を左から順に見てゆくことでこの記法を生成することです。
（１）1 はそのまま出力します。
（２）+ はスタックにプッシュします。
（３）2 はそのまま出力します。
（４）* はスタックの一番上（最も新しいもの）の演算子より優先順位が高いのでスタックにプッシュします。
（５）3 はそのまま出力します。
（６）数式が終了したときには、スタックが空になるまでポップしそれを出力します。
この動作を分かりやすく図にすると、
スタック 数式 出力
1+2*3
（１） +2*3 1
（２） + 2*3 1
（３） + *3 12
（４） +* 3 12
（５） +* 123
（６） + 123*
（６） 123*+
となります。
もう１つ上の例を頭に置いて、
1*2+3*4+5*6
の場合では、
（ １）1 はそのまま出力します。
（ ２）* はスタックが空なので無条件にスタックにプッシュします。
（ ３）2 はそのまま出力します。
（ ４）+ はスタックの一番上（最も新しいもの）の演算子 * の優先順位の方が高いのでそれをポップして出力し、+ をスタックにプッシュします。
（ ５）3 はそのまま出力します。
（ ６）* はスタックの一番上（最も新しいもの）の演算子 + より優先順位が高いのでスタックにプッシュします。
（ ７）4 はそのまま出力します。
（ ８）+ はスタックの一番上（最も新しいもの）の演算子 * の優先順位の方が高いのでそれをポップして出力し、+ をスタックにプッシュします。
（ ９）5 はそのまま出力します。
（１０）* はスタックの一番上（最も新しいもの）の演算子 + より優先順位が高いのでスタックにプッシュします。
（１１）6 はそのまま出力します。
（１２）数式が終了したときには、スタックが空になるまでポップしそれを出力します。
この動作を分かりやすく図にすると、
スタック 数式 出力
1*2+3*4+5*6
（ １） *2+3*4+5*6 1
（ ２） * 2+3*4+5*6 1
（ ３） * +3*4+5*6 12
（ ３） +3*4+5*6 12*
（ ４） + 3*4+5*6 12*
（ ５） + *4+5*6 12*3
（ ６） +* 4+5*6 12*3
（ ７） +* +5*6 12*34
（ ８） + +5*6 12*34*
（ ８） ++ 5*6 12*34*
（ ９） ++ *6 12*34*5
（１０） ++* 6 12*34*5
（１１） ++* 12*34*56
（１２） ++ 12*34*56*
（１２） + 12*34*56*+
（１２） 12*34*56*++
となります。
このことから、
・数値はそのまま出力する。
・演算子はスタックが空、またはスタックの最新のものの優先順位と同じか高いときにはプッシュし、それ以外のときにはスタックからポップたものを出力し、現在の
演算子をスタックにプッシュする。
という約束事があることが分かります。
さて、それでは実際に数式を逆ポーランド記法に変換するプログラムを考えてみましょう。ここではプログラムを簡単にするために数値は１桁、演算子は */+- のみとし、入力された数式には誤りがないということを前提にします。
#include <stdio.h>
/* 演算子と値の優先順位を定義します */
#define TOKEN_PRIORITY_MUL 2
#define TOKEN_PRIORITY_DIV 2
#define TOKEN_PRIORITY_ADD 1
#define TOKEN_PRIORITY_SUB 1
#define TOKEN_PRIORITY_VAL 0
/* トークン（語句）の構造を宣言します */
struct token_strct{
char c;
int priority;
};
/* トークン構造体を返す関数を宣言 */
struct token_strct get_token(char c);
/* メイン関数 */
main()
{
char text[80];
while(1){
gets(text);
poland(text);
}
}
/* 逆ポーランド記法で数式を表示する関数 */
poland(text)
char *text;
{
/* 出力データ用のバッファ */
struct token_strct output[80];
int loutput;
/* スタック用のバッファ */
struct token_strct stack[80];
int lstack;
struct token_strct token;
int i;
/* バッファの初期化 */
loutput= -1;
lstack = -1;
while(*text){
/* トークン構造体を取得します */
token=get_token(*text);
/* トークンが値のとき */
if(token.priority==TOKEN_PRIORITY_VAL){
output[++loutput]=token;
}
/* スタックの優先順位の方が高いとき */
else if(lstack>=0 && stack[lstack].priority>token.priority){
output[++loutput]=stack[lstack--];
stack[++lstack ]=token;
}
/* スタックが空か
スタックの演算子以上の優先順位のとき */
else{
stack[++lstack]=token;
}
text++;
}
/* 数式が終了したらスタックの内容を順次
出力バッファに追加 */
while(lstack>=0)output[++loutput]=stack[lstack--];
/* 逆ポーランド記法を表示 */
for(i=0;i<=loutput;i++)printf("%c",output[i].c);
printf("\n");
}
/* 与えられたトークンのトークン構造体を
呼び出し側に教える関数 */
struct token_strct get_token(c)
char c;
{
static struct token_strct token_table[]={
{ '*',TOKEN_PRIORITY_MUL },
{ '/',TOKEN_PRIORITY_DIV },
{ '+',TOKEN_PRIORITY_ADD },
{ '-',TOKEN_PRIORITY_SUB },
{ ' ',TOKEN_PRIORITY_VAL }
};
int i;
for(i=0;;i++){
if(token_table[i].c==c){
return token_table[i];
}
else if(token_table[i].priority==TOKEN_PRIORITY_VAL){
token_table[i].c=c;
return token_table[i];
}
}
}
ちょっと長いのですが、これまでの例の考え方をそのままプログラムにしているのでそれほど難しくはないと思います。
次に演算の順番を返るカッコ ( ) を使用できるようにしてみましょう。
まず演算子の優先順位に
#define TOKEN_PRIORITY_LBR 10
#define TOKEN_PRIORITY_RBR -10
を追加します。TOKEN_PRIORITY_LBR は左カッコ、TOKEN_PRIORITY_RBR は右カッコのときの優先順位です。この値は実際には優先順位そのものには使用せず、カッコ内の演算子の優先順位を上げるために使用します。またこの定数の値は他の演算子の最大値よりも大きい値ならばどんな値でも構いませんので、ここでは分かりやすく 10 としています。ですので、
(1+2)*3
という数式のときには次のような演算子の優先順位として処理するようにプログラムを
変更します。
( 1 + 2 ) * 3
| |
11 2
次のものが変更を加えたプログラムです。
#include <stdio.h>
/* カッコの優先順位を追加 */
#define TOKEN_PRIORITY_LBR 10
#define TOKEN_PRIORITY_RBR -10
#define TOKEN_PRIORITY_MUL 2
#define TOKEN_PRIORITY_DIV 2
#define TOKEN_PRIORITY_ADD 1
#define TOKEN_PRIORITY_SUB 1
#define TOKEN_PRIORITY_VAL 0
struct token_strct{
char c;
int priority;
};
struct token_strct get_token(char c);
main()
{
char text[80];
while(1){
gets(text);
poland(text);
}
}
poland(text)
char *text;
{
struct token_strct output[80];
int loutput;
struct token_strct stack[80];
int lstack;
struct token_strct token;
/* 演算子の優先順位に加算する値を保持する
変数を追加 */
int add_priority;
int i;
loutput= -1;
lstack = -1;
/* 加算する優先順位の変数の初期化を追加 */
add_priority=0;
while(*text){
token=get_token(*text);
/* トークンが値のとき */
if(token.priority==TOKEN_PRIORITY_VAL){
output[++loutput]=token;
}
/* トークンがカッコのとき */
else if(token.priority==TOKEN_PRIORITY_LBR
|| token.priority==TOKEN_PRIORITY_RBR){
add_priority+=token.priority;
}
/* トークンが演算子のとき */
else{
/* 演算子の優先順位を調整します */
token.priority+=add_priority;
if(lstack>=0 && stack[lstack].priority>token.priority){
output[++loutput]=stack[lstack--];
stack[++lstack ]=token;
}
else{
stack[++lstack]=token;
}
}
text++;
}
while(lstack>=0)output[++loutput]=stack[lstack--];
for(i=0;i<=loutput;i++)printf("%c",output[i].c);
printf("\n");
}
struct token_strct get_token(c)
char c;
{
/* トークンのテーブルに ( ) を追加 */
static struct token_strct token_table[]={
{ '(',TOKEN_PRIORITY_LBR },
{ ')',TOKEN_PRIORITY_RBR },
{ '*',TOKEN_PRIORITY_MUL },
{ '/',TOKEN_PRIORITY_DIV },
{ '+',TOKEN_PRIORITY_ADD },
{ '-',TOKEN_PRIORITY_SUB },
{ ' ',TOKEN_PRIORITY_VAL }
};
int i;
for(i=0;;i++){
if(token_table[i].c==c){
return token_table[i];
}
else if(token_table[i].priority==TOKEN_PRIORITY_VAL){
token_table[i].c=c;
return token_table[i];
}
}
}
実際にこのプログラムで実行してみると、
((1+2)*(3+4)+5)*6
のときに、
12+34+5+6**
となってしまい、結果が正しくありません。一体何が間違っているのかを図にして考え
てみましょう。
加算値 スタック 数式 出力
0 ((1+2)*(3+4)+5)*6
10 (1+2)*(3+4)+5)*6
20 1+2)*(3+4)+5)*6
20 +2)*(3+4)+5)*6 1
20 +(21) 2)*(3+4)+5)*6 1
20 +(21) )*(3+4)+5)*6 12
10 +(21) *(3+4)+5)*6 12
10 *(3+4)+5)*6 12+
10 *(12) (3+4)+5)*6 12+
20 *(12) 3+4)+5)*6 12+
20 *(12) +4)+5)*6 12+3
20 *(12)+(21) 4)+5)*6 12+3
20 *(12)+(21) )+5)*6 12+34
10 *(12)+(21) +5)*6 12+34 ー（１）
10 *(12) +5)*6 12+34+ ー（２）
10 *(12)+(11) 5)*6 12+34+ ー（３）
10 *(12)+(11) )*6 12+34+5
0 *(12)+(11) *6 12+34+5
0 *(12) *6 12+34+5+
0 *(12)*(2) 6 12+34+5+
0 *(12)*(2) 12+34+5+6
0 *(12) 12+34+5+6*
0 12+34+5+6**
となっています。問題は、上図の（１）の部分で優先順位が 11 となる演算子 + を処理するときに、スタックには優先順位 21 の演算子 + をポップして出力し、この優先順位11 の + をスタックにプッシュしている部分です。その結果（３）でのスタック内の優先順位が最新のものより古いものの方が高くなってしまっています。
ということは最初に決めた約束事を次のように変更する必要があります。
・数値はそのまま出力する。
・演算子はスタックが空、またはスタックの最新のものの優先順位と同じか高いときにはプッシュし、それ以外のときにはスタックの優先順位の方が高い間は、スタックからポップたものを出力することを繰り返し、現在の演算子をスタックにプッシュする。
この規則でもう一度考え直してみると、
加算値 スタック 数式 出力
0 ((1+2)*(3+4)+5)*6
10 (1+2)*(3+4)+5)*6
20 1+2)*(3+4)+5)*6
20 +2)*(3+4)+5)*6 1
20 +(21) 2)*(3+4)+5)*6 1
20 +(21) )*(3+4)+5)*6 12
10 +(21) *(3+4)+5)*6 12
10 *(3+4)+5)*6 12+
10 *(12) (3+4)+5)*6 12+
20 *(12) 3+4)+5)*6 12+
20 *(12) +4)+5)*6 12+3
20 *(12)+(21) 4)+5)*6 12+3
20 *(12)+(21) )+5)*6 12+34
10 *(12)+(21) +5)*6 12+34
10 *(12) +5)*6 12+34+
10 +5)*6 12+34+*
10 +(11) 5)*6 12+34+*
10 +(11) )*6 12+34+*5
0 +(11) *6 12+34+*5
0 *6 12+34+*5+
0 *(2) 6 12+34+*5+
0 *(2) 12+34+*5+6
0 12+34+*5+6*
となるので、この改定した規則は正しいようです。この規則を基にもう一度プログラムを改修します。
#include <stdio.h>
#define TOKEN_PRIORITY_LBR 10
#define TOKEN_PRIORITY_RBR -10
#define TOKEN_PRIORITY_MUL 2
#define TOKEN_PRIORITY_DIV 2
#define TOKEN_PRIORITY_ADD 1
#define TOKEN_PRIORITY_SUB 1
#define TOKEN_PRIORITY_VAL 0
struct token_strct{
char c;
int priority;
};
struct token_strct get_token(char c);
main()
{
char text[80];
while(1){
gets(text);
poland(text);
}
}
poland(text)
char *text;
{
struct token_strct output[80];
int loutput;
struct token_strct stack[80];
int lstack;
struct token_strct token;
int add_priority;
int i;
loutput= -1;
lstack = -1;
add_priority=0;
while(*text){
token=get_token(*text);
if(token.priority==TOKEN_PRIORITY_VAL){
output[++loutput]=token;
}
else if(token.priority==TOKEN_PRIORITY_LBR
|| token.priority==TOKEN_PRIORITY_RBR){
add_priority+=token.priority;
}
else{
token.priority+=add_priority;
/* スタックが空か、スタックの優先順位が同じか低いとき */
if(lstack== -1 || stack[lstack].priority<=token.priority){
stack[++lstack]=token;
}
/* スタックの優先順位の方が高いとき */
else{
/* スタックが空でなく優先順位が高い間はポップして
出力バッファに追加します */
while(lstack>=0 && stack[lstack].priority>token.priority){
output[++loutput]=stack[lstack--];
}
stack[++lstack]=token;
}
}
text++;
}
while(lstack>=0)output[++loutput]=stack[lstack--];
for(i=0;i<=loutput;i++)printf("%c",output[i].c);
printf("\n");
}
struct token_strct get_token(c)
char c;
{
static struct token_strct token_table[]={
{ '(',TOKEN_PRIORITY_LBR },
{ ')',TOKEN_PRIORITY_RBR },
{ '*',TOKEN_PRIORITY_MUL },
{ '/',TOKEN_PRIORITY_DIV },
{ '+',TOKEN_PRIORITY_ADD },
{ '-',TOKEN_PRIORITY_SUB },
{ ' ',TOKEN_PRIORITY_VAL }
};
int i;
for(i=0;;i++){
if(token_table[i].c==c){
return token_table[i];
}
else if(token_table[i].priority==TOKEN_PRIORITY_VAL){
token_table[i].c=c;
return token_table[i];
}
}
}
このようにして四則演算の数式を逆ポーランド記法に変換するプログラムができました。ここで紹介した例はあくまでアルゴリズムを分かりやすくするためのものですので、もし実用のプログラムで逆ポーランド記法を生成しなければならないときには、入力された数式のフォーマットの検査、２文字以上の数値と演算子の処理、符号を反転するマイナス記号（単項演算子）の処理などを行なわなければなりません。
このように演算の優先順位を考慮しないで計算のできる逆ポーランド記法は、現在の実際のコンパイラでは、そのままコードの生成に使用されることは殆どありません。というのも逆ポーランド記法ではコードの最適化を行なうには不便な表現方法だからです。実際には『２つ組み』や『３つ組み』と呼ばれる表現にした後、最適化を行っています。例えば、
(a+b)*(a+b)+(a+b)
を、
３つ組み
(a+b)*(a+b)+(a+b) → t1*(a+b)+(a+b) t1=a+b
t1*(a+b)+(a+b) → t1*t2+(a+b) t2=a+b
t1*t2+(a+b) → t1*t2+t3 t3=a+b
t1*t2+t3 → t4+t3 t4=t1*t2
t4+t3 → t5 t5=t4+t3
とし、この３つ組みコードで最適化を行ないます。この場合、t1、t2、t3 は同じ値になりますので、t2 と t3 を t1 で置き換え、不要な３つ組みを削除すると、
t1=a+b
t4=t1*t1
t5=t4+t1
となるので、共通部分式の最適化を行なえるようになります。
コンパイラでは生成したコードが小さくて高速に動作することを目的としますので、逆ポーランド記法は適していませんが、アプリケーションプログラムの中で数式を処理するときには便利ですので理解しておくことをお勧めします。
それではまた次回。
