操車場アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』
操車場アルゴリズム（そうしゃじょうあるごりずむ）は、計算機科学において、中置記法の数式を構文解析する技法である。逆ポーランド記法 (RPN) または抽象構文木 (AST) の形式で出力を生成するのに使える。このアルゴリズムはエドガー・ダイクストラが考案したもので、鉄道の操車場に似た操作をするため、このような名称がつけられた。ダイクストラが操車場アルゴリズムを最初に発表したのは、Centrum Wiskunde（オランダ国立数学研究所）のレポート MR 34/61 である（1961年）[1]。
RPNの評価技法と同様、操車場アルゴリズムはスタックに基づいている。中置記法の数式は最も一般的な数学的記法であり、例えば 3+4 や 3+4*(2−1) がそうである。変換に際して、入力用と出力用の2つのテキスト変数（文字列）を使用する。他に出力キューに追加する前の演算子を保持するスタックが必要である。入力文字列からシンボル（トークン）を順次読み出し、その後もシンボル単位で処理を行う。
操車場アルゴリズムを後に一般化したのが演算子順位構文解析である。
目次 |
[編集] 単純な変換例
- 入力: 3+4
- 3 を出力キューに追加する（数値は常に出力にそのまま送られる）。
- + （またはそのID）を演算子スタックにプッシュする。
- 4 を出力キューに追加する。
- 式を読み終わったので、スタックにある演算子群をポップし、出力キューに追加する。この例では "+" だけがスタックにある。
- "3 4 +" が出力となる。
この例で、いくつかの規則が示されている。
- 全ての数値は読み込まれた時点で出力に追加される。
- 式を読み終わったら、スタックから全演算子をポップし、出力に追加していく。
[編集] アルゴリズムの詳細
- 読み込むべきトークンがある間、以下を繰り返す。
- トークンを1つ読み込む。
- トークンが数値の場合、それを出力キューに追加する。
- トークンが関数の場合、それをスタックにプッシュする。
- トークンが関数の引数セパレータ（カンマなど）の場合
- スタックのトップにあるトークンが左括弧となるまで、スタックから演算子をポップして出力キューに追加する動作を繰り返す。左括弧が出てこない場合、引数セパレータの位置がおかしいか、左右の括弧が不一致となっている（エラー）。
- トークンが演算子 o1 の場合
- トークンが左括弧の場合、スタックにプッシュする。
- トークンが右括弧の場合
- スタックのトップにあるトークンが左括弧になるまで、スタックからポップした演算子を出力キューに追加する動作を繰り返す。
- 左括弧をスタックからポップするが、出力には追加せずに捨てる。
- スタックのトップにあるトークンが関数トークンなら、それをポップして出力キューに追加する。
- 左括弧がスタック上に見つからなかった場合、左右の括弧の不一致がある（エラー）。
- 読み込むべきトークンがない場合
- スタック上に演算子トークンがある間、以下を繰り返す。
- スタックのトップにある演算子トークンが括弧なら、括弧の不一致がある（エラー）。
- 演算子をスタックからポップして出力キューに追加する。
- スタック上に演算子トークンがある間、以下を繰り返す。
- 終了
このアルゴリズムの実行時の複雑性（計算量）の分析にあたり注目すべき点は、各トークンがそれぞれ一度しか読まれず、数値も関数も演算子も一度だけしか出力されず、関数・演算子・括弧はそれぞれ一度スタックにプッシュされ後にポップされるという点である。したがって、トークン毎の操作回数はせいぜい定数値であり、実行時間は O(n)、つまり入力の大きさに比例する。
操車場アルゴリズムは前置記法（ポーランド記法）の生成にも使える。その場合は、入力トークン列を最後尾から先頭に向かって処理し、出力キューを反転させ（つまり、出力キューは出力スタックとなる）、右括弧と左括弧の扱いを反転させればよい（つまり、左括弧については右括弧を見つけるまでスタックをポップし続ける）。
[編集] 詳細な実施例
| 演算子 | 優先順位 | 結合性 |
|---|---|---|
| ^ | 4 | 右 |
| * | 3 | 左 |
| / | 3 | 左 |
| + | 2 | 左 |
| - | 2 | 左 |
| トークン | 動作 | 出力 (RPN) | 演算子スタック | 備考 |
|---|---|---|---|---|
| 3 | トークンを出力に追加 | 3 | ||
| + | トークンをスタックにプッシュ | 3 | + | |
| 4 | トークンを出力に追加 | 3 4 | + | |
| * | トークンをスタックにプッシュ | 3 4 | * + | * は ＋ より優先順位が高い |
| 2 | トークンを出力に追加 | 3 4 2 | * + | |
| / | スタックからポップして出力へ | 3 4 2 * | + | / と * の優先順位は同じ |
| トークンをスタックにプッシュ | 3 4 2 * | / + | / は ＋ より優先順位が高い | |
| ( | トークンをスタックにプッシュ | 3 4 2 * | ( / + | |
| 1 | トークンを出力に追加 | 3 4 2 * 1 | ( / + | |
| − | トークンをスタックにプッシュ | 3 4 2 * 1 | − ( / + | |
| 5 | トークンを出力に追加 | 3 4 2 * 1 5 | − ( / + | |
| ) | スタックからポップして出力へ | 3 4 2 * 1 5 − | ( / + | "(" が見つかるまで繰り返す |
| スタックからポップ | 3 4 2 * 1 5 − | / + | マッチした括弧を捨てる | |
| ^ | トークンをスタックにプッシュ | 3 4 2 * 1 5 − | ^ / + | ^ は / より優先順位が高い |
| 2 | トークンを出力に追加 | 3 4 2 * 1 5 − 2 | ^ / + | |
| ^ | トークンをスタックにプッシュ | 3 4 2 * 1 5 − 2 | ^ ^ / + | ^ は右結合性 |
| 3 | トークンを出力に追加 | 3 4 2 * 1 5 − 2 3 | ^ ^ / + | |
| end | スタックから出力へ全部をポップ | 3 4 2 * 1 5 − 2 3 ^ ^ / + |
インタプリタでこれを使う場合、この出力を字句解析して中間ファイルに書き込み、それをインタプリタが解釈実行する。中置記法からRPNへの変換は、数式を簡単に単純化するのにも使える。そのためにはRPNの式を評価するようにし、値がヌルの変数が出てきたり、値がヌルの演算子が出てきたら、そのパラメータと共に出力に書き込めばよい（これは単純化であり、パラメータが別の演算子だった場合には問題が生じる）。ヌルのパラメータがない演算子の場合は、単にその値を出力に書き込めばよい。この技法は明らかにあらゆる単純化を含んでいるわけではない。それは定数畳み込みの最適化に近い。
[編集] C言語での実装例
#include <string.h> #include <stdio.h> #define bool int #define false 0 #define true 1 // 演算子 // 優先順位 : 演算子 : 結合性 // 4 : ! : 右結合性 // 3 : * / % : 左結合性 // 2 : + - : 左結合性 // 1 : = : 右結合性 int op_preced(const char c) { switch(c) { case '!': return 4; case '*': case '/': case '%': return 3; case '+': case '-': return 2; case '=': return 1; } return 0; } bool op_left_assoc(const char c) { switch(c) { // 左結合性 case '*': case '/': case '%': case '+': case '-': return true; // 右結合性 case '=': case '!': return false; } return false; } unsigned int op_arg_count(const char c) { switch(c) { 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(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')) bool shunting_yard(const char *input, char *output) { const char *strpos = input, *strend = input + strlen(input); char c, *outpos = output; char stack[32]; // 演算子スタック unsigned int sl = 0; // スタック長（深さ） char sc; // スタック要素の記録用 while(strpos < strend) { // 入力ストリームからトークンを1つ読み込む c = *strpos; if(c != ' ') { // トークンが数値（識別子）なら、出力キューに追加する if(is_ident(c)) { *outpos = c; ++outpos; } // トークンが関数なら、スタックにプッシュする。 else if(is_function(c)) { stack[sl] = c; ++sl; } // トークンが関数の引数のセパレータ（例えばカンマ）の場合 else if(c == ',') { bool pe = false; while(sl > 0) { sc = stack[sl - 1]; if(sc == '(') { pe = true; break; } else { // スタックのトップのトークンが左括弧になるまで // スタック上の演算子を出力キューにポップし続ける *outpos = sc; ++outpos; sl--; } } // 左括弧が出てこなかった場合、すなわちセパレータの位置が変だった場合 // あるいは括弧が正しく対応していない場合 if(!pe) { printf("Error: separator or parentheses mismatched\n"); return false; } } // トークンが演算子 op1 の場合 else if(is_operator(c)) { 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; ++outpos; sl--; } else { break; } } // op1 をスタックにプッシュ stack[sl] = c; ++sl; } // トークンが左括弧なら、スタックにプッシュ else if(c == '(') { stack[sl] = c; ++sl; } // トークンが右括弧の場合 else if(c == ')') { bool pe = false; // スタックのトップにあるトークンが左括弧になるまで // スタックから出力キューに演算子をポップし続ける while(sl > 0) { sc = stack[sl - 1]; if(sc == '(') { pe = true; break; } else { *outpos = sc; ++outpos; sl--; } } // スタックを全部見ても左括弧に到達しなかった場合、左右の括弧の不一致があることになる if(!pe) { printf("Error: parentheses mismatched\n"); return false; } // スタックから左括弧をポップするが、出力キューには置かない sl--; // スタックのトップにあるトークンが関数トークンなら、それを出力キューにポップする if(sl > 0) { sc = stack[sl - 1]; if(is_function(sc)) { *outpos = sc; ++outpos; sl--; } } } else { printf("Unknown token %c\n", c); return false; // 不明なトークン } } ++strpos; } // 読み込むべきトークンが尽きた際 // スタック上に演算子トークンが残っていたら、それらを出力する while(sl > 0) { sc = stack[sl - 1]; if(sc == '(' || sc == ')') { printf("Error: parentheses mismatched\n"); return false; } *outpos = sc; ++outpos; --sl; } *outpos = 0; // ヌルでターミネート return true; } bool execution_order(const char *input) { printf("order:\n"); const char *strpos = input, *strend = input + strlen(input); char c, res[4]; unsigned int sl = 0, sc, stack[32], rn = 0; // 入力トークンがある間ループする while(strpos < strend) { // 入力から次のトークンを読み込む c = *strpos; // トークンが値か識別子の場合 if(is_ident(c)) { // それをスタックにプッシュする。 stack[sl] = c; ++sl; } // さもなくば、トークンは演算子である（ここでは関数も演算子に含める） else if(is_operator(c) || is_function(c)) { sprintf(res, "_%02d", rn); printf("%s = ", res); ++rn; // 演算子が n 個の引数をとることは事前にわかっている。 unsigned int nargs = op_arg_count(c); // スタックに n 個未満の値しかない場合 if(sl < nargs) { // ユーザーの入力した式に値（引数）が足りないのでエラーを返す return false; } // そうでない場合、スタックから n 個の値をポップする // それらの値を引数として、演算子を評価する if(is_function(c)) { printf("%c(", c); while(nargs > 0){ sc = stack[sl - nargs]; // 逆順の引数を削除 if(nargs > 1) { printf("%s, ", &sc); } else { printf("%s)\n", &sc); } --nargs; } sl-=op_arg_count(c); } else { if(nargs == 1) { sc = stack[sl - 1]; sl--; printf("%c %s;\n", c, &sc); } else { sc = stack[sl - 2]; printf("%s %c ", &sc, c); sc = stack[sl - 1]; sl--;sl--; printf("%s;\n",&sc); } } // 返ってきた結果がもしあれば、スタックにプッシュ stack[sl] = *(unsigned int*)res; ++sl; } ++strpos; } // スタックに1つの値しかない場合、 // その値が計算結果である。 if(sl == 1) { sc = stack[sl - 1]; sl--; printf("%s is a result\n", &sc); return true; } // スタックにさらに値がある場合 // ユーザ入力に値が多すぎるので、エラーとする。 return false; } int main() { // 関数: A() B(a) C(a, b), D(a, b, c) ... // 識別子: 0 1 2 3 ... および a b c d e ... // 演算子: = - + / * % ! const char *input = "a = D(f - b * c + d, !e, g)"; char output[128]; printf("input: %s\n", input); if(shunting_yard(input, output)) { printf("output: %s\n", output); if(!execution_order(output)) printf("\nInvalid input\n"); } return 0; }
このコードは次のような結果を出力する。
input: a = D(f - b * c + d, !e, g)
output: afbc*-d+e!gD=
order:
_00 = b * c;
_01 = f - _00;
_02 = _01 + d;
_03 = ! e;
_04 = D(_02, _03, g)
_05 = a = _04;
_05 is a result
[編集] 脚注
- ^ Dijkstra, E.W. (1961). Algol 60 translation : An algol 60 translator for the x1 and making a translator for algol 60. Stichting Mathematisch Centrum.
[編集] 外部リンク
- 操車場アルゴリズムについてのダイクストラの最初の論文
- Parsing Expressions by Recursive Descent Theodore Norvell © 1999–2001. Access date September 14, 2006.
- Extension to the ‘Shunting Yard’ algorithm to allow variable numbers of arguments to functions
オンラインデモ:
実装例:
