操車場アルゴリズム

単純な変換例

アルゴリズムの詳細

詳細な実施例

C言語での実装例

#include<string.h>
#include<stdio.h>
#include<stdbool.h>

// 演算子
// 優先順位 : 演算子 : 結合性
// 4 :  !  : 右結合性
// 3 : * / % : 左結合性
// 2 : + -  : 左結合性
// 1 : =  : 右結合性
intop_preced(constcharc)
{
switch(c){
case'!':
return4;
case'*':case'/':case'%':
return3;
case'+':case'-':
return2;
case'=':
return1;
}
return0;
}

boolop_left_assoc(constcharc)
{
switch(c){
// 左結合性
case'*':case'/':case'%':case'+':case'-':
returntrue;
// 右結合性
case'=':case'!':
returnfalse;
}
returnfalse;
}

unsignedintop_arg_count(constcharc)
{
switch(c){
case'*':case'/':case'%':case'+':case'-':case'=':
return2;
case'!':
return1;
default:// 関数の場合、A()の引数は0個、B()の引数は1個、C()の引数は2個... と定義
returnc-'A';
}
return0;
}

#define is_operator(c) (c == '+' || c == '-' || c == '/' || c == '*' || c == '!' || c == '%' || c == '=')
#define is_function(c) (c >= 'A' && c <= 'Z')
#define is_ident(c) ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z'))

boolshunting_yard(constchar*input,char*output)
{
constchar*strpos=input,*strend=input+strlen(input);
charc,*outpos=output;

charstack[32];// 演算子スタック
unsignedintsl=0;// スタック長(深さ)
charsc;// スタック要素の記録用

while(strpos<strend){
// 入力ストリームからトークンを1つ読み込む
c=*strpos++;
if(c==' '){
continue;
}elseif(is_ident(c)){
// トークンが数値(識別子)なら、出力キューに追加する
*outpos++=c;
}elseif(is_function(c)){
// トークンが関数なら、スタックにプッシュする。
stack[sl++]=c;
}elseif(c==','){
// トークンが関数の引数のセパレータ(例えばカンマ)の場合
boolpe=false;
while(sl>0){
sc=stack[sl-1];
if(sc=='('){
pe=true;
break;
}else{
// スタックのトップのトークンが左括弧になるまで
// スタック上の演算子を出力キューにポップし続ける
*outpos++=sc;
sl--;
}
}
// 左括弧が出てこなかった場合、すなわちセパレータの位置が変だった場合
// あるいは括弧が正しく対応していない場合
if(!pe){
printf("エラー:セパレータか括弧の不一致\n");
returnfalse;
}
}elseif(is_operator(c)){
// トークンが演算子 op1 の場合
while(sl>0){
sc=stack[sl-1];
// op1 が左結合性で優先順位が op2 と等しいか低い場合
// あるいは op1 の優先順位が op2 より低い場合
// 演算子トークン op2 がスタックのトップにある間ループする。
// 1^2+3 のような式を正しく 12^3+ に変換するため
// "+" と "^" は右結合性とする。
// 演算子の優先順位の違いからポップするかプッシュするかを判断する。
// 2つの演算子の優先順位が等しいなら、結合性から判断する。
if(is_operator(sc)&&
((op_left_assoc(c)&&(op_preced(c)<=op_preced(sc)))||
(op_preced(c)<op_preced(sc)))){
// Pop op2 off the stack, onto the output queue;
*outpos++=sc;
sl--;
}else{
break;
}
}
// op1 をスタックにプッシュ
stack[sl++]=c;
}elseif(c=='('){
// トークンが左括弧なら、スタックにプッシュ
stack[sl++]=c;
}elseif(c==')'){
// トークンが右括弧の場合
boolpe=false;
// スタックのトップにあるトークンが左括弧になるまで
// スタックから出力キューに演算子をポップし続ける
while(sl>0){
sc=stack[--sl];
if(sc=='('){
// スタックから左括弧をポップするが、出力キューには置かない
pe=true;
break;
}else{
*outpos++=sc;
}
}
// スタックを全部見ても左括弧に到達しなかった場合、左右の括弧の不一致があることになる
if(!pe){
printf("エラー:括弧の不一致\n");
returnfalse;
}
// スタックのトップにあるトークンが関数トークンなら、それを出力キューにポップする
if(sl>0){
sc=stack[sl-1];
if(is_function(sc)){
*outpos++=sc;
sl--;
}
}
}else{
printf("不明なトークン:%c\n",c);
returnfalse;// 不明なトークン
}
}
// 読み込むべきトークンが尽きた際
// スタック上に演算子トークンが残っていたら、それらを出力する
while(sl>0){
sc=stack[--sl];
if(sc=='('||sc==')'){
printf("エラー:括弧の不一致\n");
returnfalse;
}
*outpos++=sc;
}
*outpos=0;// ヌルでターミネート
returntrue;
}

boolexecution_order(constchar*input)
{
constchar*strpos=input,*strend=input+strlen(input);
charc,res[4];
unsignedintsl=0,sc,stack[32],rn=0;
printf("【実行順序】\n");
// 入力トークンがある間ループする
while(strpos<strend){
// 入力から次のトークンを読み込む
c=*strpos++;
if(is_ident(c)){
// トークンが値か識別子の場合
// それをスタックにプッシュする。
stack[sl++]=c;
}elseif(is_operator(c)||is_function(c)){
// さもなくば、トークンは演算子である(ここでは関数も演算子に含める)
sprintf(res,"$%d",rn++);
printf("%s = ",res);
// 演算子が n 個の引数をとることは事前にわかっている。
unsignedintnargs=op_arg_count(c);
if(sl<nargs){
// スタックに n 個未満の値しかない場合
// ユーザーの入力した式に値(引数)が足りないのでエラーを返す
returnfalse;
}
// そうでない場合、スタックから n 個の値をポップする
// それらの値を引数として、演算子を評価する
if(is_function(c)){
printf("%c(",c);
while(nargs>0){
sc=stack[sl-nargs];// 逆順の引数を削除
if(nargs>1){
printf("%s, ",(char*)&sc);
}else{
printf("%s);\n",(char*)&sc);
}
--nargs;
}
sl-=op_arg_count(c);
}else{
if(nargs==1){
sc=stack[--sl];
printf("%c %s;\n",c,(char*)&sc);
}else{
sc=stack[sl-2];
printf("%s %c ",(char*)&sc,c);
sc=stack[sl-1];
sl-=2;
printf("%s;\n",(char*)&sc);
}
}
// 返ってきた結果がもしあれば、スタックにプッシュ
stack[sl++]=*(unsignedint*)res;
}
}
// スタックに1つの値しかない場合、
// その値が計算結果である。
if(sl==1){
sc=stack[--sl];
printf("実行結果は %s\n",(char*)&sc);
returntrue;
}
// スタックにさらに値がある場合
// ユーザ入力に値が多すぎるので、エラーとする。
returnfalse;
}

intmain()
{
// 関数: A() B(a) C(a, b), D(a, b, c) ...
// 識別子: 0 1 2 3 ... および a b c d e ...
// 演算子: = - + / * % !
constchar*input="a = D(f - b * c + d, !e, g)";
charoutput[128];
printf("【入力】\n%s\n\n",input);
if(shunting_yard(input,output)){
printf("【出力】\n%s\n\n",output);
if(!execution_order(output)){
printf("\n不正な入力\n");
}
}
return0;
}

脚注

1. ^ 日本では近年はほとんど行われなくなったが、旧来の鉄道貨物列車は、まず出発駅から拠点駅に集められ、その後は拠点駅から拠点駅の間を車輛1輛ごとに目的地別に何度か再編成されながら、目的地へ向かう、というものであった。なお余談になるが、考案者のダイクストラには他にも、排他制御機構の「セマフォ」(やはり昔の鉄道で一般的だった腕木式信号機に由来する)など、鉄道関係のたとえが多い。
2. ^ Dijkstra, E.W. (1961). Algol 60 translation : An algol 60 translator for the x1 and making a translator for algol 60. Stichting Mathematisch Centrum. http://repository.cwi.nl/search/fullrecord.php?publnr=9251 . 

外部リンク