操車場アルゴリズム

操車場アルゴリズムは、なんらかの中置記法に属する構文に従った順序で記号が並んでいる、数式等の記号列を解析する、スタックベースのアルゴリズムである。その出力を出力順にそのまま並べれば逆ポーランド記法  になるし、あるいは抽象構文木を構築したり、数値と四則演算等の算術式のようなものであればその場で直接計算結果を得てしまってもよい。エドガー・ダイクストラが考案したもので、鉄道の入れ替えとして説明したことから、操車場という名称がつけられた。初出は、Centrum Wiskundeのレポート MR 34/61 である。

データフローとして見ると、このアルゴリズムには、入力と出力の2つの記号の列があり、その他に1つ、演算子を保持するスタックとして使われる列がある。入力から記号を順次読み出し、その記号とスタックトップの記号に応じて、入力の記号を直接出力に送るか、スタックに積むか、入力を一旦そのままホールドしてスタックトップを取り出して出力に送るか、という動作をする。

操車場アルゴリズムを後に一般化したのが演算子順位構文解析器である。

1. 単純な変換例
---------

入力: 3+4

3 を出力キューに追加する。
+ を演算子スタックにプッシュする。
4 を出力キューに追加する。
式を読み終わったので、スタックにある演算子群をポップし、出力キューに追加する。この例では "+" だけがスタックにある。
"3 4 +" が出力となる。この例で、いくつかの規則が示されている。

全ての数値は読み込まれた時点で出力に追加される。
式を読み終わったら、スタックから全演算子をポップし、出力に追加していく。

2. アルゴリズムの詳細
------------

読み込むべきトークンがある間、以下を繰り返す。
トークンを1つ読み込む。
トークンが数値の場合、それを出力キューに追加する。
トークンが関数の場合、それをスタックにプッシュする。
トークンが関数の引数セパレータの場合
スタックのトップにあるトークンが左括弧となるまで、スタックから演算子をポップして出力キューに追加する動作を繰り返す。左括弧が出てこない場合、引数セパレータの位置がおかしいか、左右の括弧が不一致となっている。
トークンが演算子 o1 の場合
スタックのトップに演算子トークン o2 があり、o1 が演算子の結合性で、かつ優先順位が o2 と等しいか低い場合、あるいは、o1 の優先順位が o2 より低い場合、以下を繰り返す。
o2 をスタックからポップし、出力キューに追加する。
o1 をスタックにプッシュする。
トークンが左括弧の場合、スタックにプッシュする。
トークンが右括弧の場合
スタックのトップにあるトークンが左括弧になるまで、スタックからポップした演算子を出力キューに追加する動作を繰り返す。
左括弧をスタックからポップするが、出力には追加せずに捨てる。
スタックのトップにあるトークンが関数トークンなら、それをポップして出力キューに追加する。
左括弧がスタック上に見つからなかった場合、左右の括弧の不一致がある。
読み込むべきトークンがない場合
スタック上に演算子トークンがある間、以下を繰り返す。
スタックのトップにある演算子トークンが括弧なら、括弧の不一致がある。
演算子をスタックからポップして出力キューに追加する。
終了このアルゴリズムの実行時の複雑性の分析にあたり注目すべき点は、各トークンがそれぞれ一度しか読まれず、数値も関数も演算子も一度だけしか出力されず、関数・演算子・括弧はそれぞれ一度スタックにプッシュされ後にポップされるという点である。したがって、トークン毎の操作回数はせいぜい定数値であり、実行時間は O、つまり入力の大きさに比例する。

操車場アルゴリズムは前置記法の生成にも使える。その場合は、入力トークン列を最後尾から先頭に向かって処理し、出力キューを反転させ、右括弧と左括弧の扱いを反転させればよい。

3. 詳細な実施例
---------

中置記法からRPNへの変換は、数式を簡単に単純化するのにも使える。そのためにはRPNの式を評価するようにし、値がヌルの変数が出てきたり、値がヌルの演算子が出てきたら、そのパラメータと共に出力に書き込めばよい。ヌルのパラメータがない演算子の場合は、単にその値を出力に書き込めばよい。この技法は明らかにあらゆる単純化を含んでいるわけではない。それは定数畳み込みの最適化に近い。

4. C言語での実装例
-----------

include
include
include // 演算子 // 優先順位 : 演算子 : 結合性 // 4 : ! : 右結合性 // 3 : * / % : 左結合性 // 2 : + - : 左結合性 // 1 : = : 右結合性 int op_preced { switch  { case '!': return 4; case '*': case '/': case '%': return 3; case '+': case '-': return 2; case '=': return 1; } return 0; }

bool op_left_assoc { switch  { // 左結合性 case '*': case '/': case '%': case '+': case '-': return true; // 右結合性 case '=': case '!': return false; } return false; }

unsigned int op_arg_count { switch  { case '*': case '/': case '%': case '+': case '-': case '=': return 2; case '!': return 1; default: // 関数の場合、Aの引数は0個、Bの引数は1個、Cの引数は2個... と定義 return c - 'A'; } return 0; }

define is_operator 
define is_function 
define is_ident  || )bool shunting_yard { const char *strpos = input, *strend = input + strlen; char c, *outpos = output;

char stack[32]; // 演算子スタック unsigned int sl = 0; // スタック長 char sc; // スタック要素の記録用

while  { // 入力ストリームからトークンを1つ読み込む c = *strpos++; if  { continue; } else if ) { // トークンが数値なら、出力キューに追加する

outpos++ = c;} else if ) { // トークンが関数なら、スタックにプッシュする。 stack[sl++] = c; } else if  { // トークンが関数の引数のセパレータの場合 bool pe = false; while  { sc = stack[sl - 1]; if  { pe = true; break; } else { // スタックのトップのトークンが左括弧になるまで // スタック上の演算子を出力キューにポップし続ける

outpos++ = sc;sl--; } } // 左括弧が出てこなかった場合、すなわちセパレータの位置が変だった場合 // あるいは括弧が正しく対応していない場合 if  { printf; return false; } } else if ) { // トークンが演算子 op1 の場合 while  { sc = stack[sl - 1]; // op1 が左結合性で優先順位が op2 と等しいか低い場合 // あるいは op1 の優先順位が op2 より低い場合 // 演算子トークン op2 がスタックのトップにある間ループする。 // 1^2+3 のような式を正しく 12^3+ に変換するため // "+" と "^" は右結合性とする。 // 演算子の優先順位の違いからポップするかプッシュするかを判断する。 // 2つの演算子の優先順位が等しいなら、結合性から判断する。 if  &&  &&  <= op_preced)) ||  < op_preced))) { // Pop op2 off the stack, onto the output queue;

outpos++ = sc;sl--; } else { break; } } // op1 をスタックにプッシュ stack[sl++] = c; } else if  { // トークンが左括弧なら、スタックにプッシュ stack[sl++] = c; } else if ') { // トークンが右括弧の場合 bool pe = false; // スタックのトップにあるトークンが左括弧になるまで // スタックから出力キューに演算子をポップし続ける while  { sc = stack[--sl]; if  { // スタックから左括弧をポップするが、出力キューには置かない pe = true; break; } else {

outpos++ = sc;} } // スタックを全部見ても左括弧に到達しなかった場合、左右の括弧の不一致があることになる if  { printf; return false; } // スタックのトップにあるトークンが関数トークンなら、それを出力キューにポップする if  { sc = stack[sl - 1]; if ) {

outpos++ = sc;sl--; } } } else { printf; return false; // 不明なトークン } } // 読み込むべきトークンが尽きた際 // スタック上に演算子トークンが残っていたら、それらを出力する while  { sc = stack[--sl]; if ') { printf; return false; }

outpos++ = sc;}

outpos = 0; // ヌルでターミネートreturn true; }

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

int main { // 関数: A B C, D ... // 識別子: 0 1 2 3 ... および a b c d e ... // 演算子: = - + / * % ! const char *input = "a = D"; char output[128]; printf("【入力】 %s

", input); if ) { printf("【出力】 %s

", output); if ) { printf; } } return 0; }<WtXmlEndTag />

このコードは次のような結果を出力する。 【入力】 a = D

【出力】 afbc*-d+e!gD=

【実行順序】 $0 = b * c; $1 = f - $0; $2 = $1 + d; $3 = ! e; $4 = D; $5 = a = $4; 実行結果は $5

5. 脚注
-----

6. 外部リンク
--------

[1]
[2] Theodore Norvell © 1999–2001. Access date September 14, 2006.
[3]オンラインデモ:

[4]
[5]実装例:

[6]
[7]
[8] その2
[9]