操車場アルゴリズム
操車場アルゴリズム（そうしゃじょうアルゴリズム）は、なんらかの中置記法に属する構文に従った順序で記号（トークン）が並んでいる、数式等の記号列を解析（構文解析）する、スタックベースのアルゴリズムである。その出力を出力順にそのまま並べれば逆ポーランド記法 (RPN) になるし、あるいは抽象構文木を構築したり、数値と四則演算等の算術式のようなものであればその場で直接計算結果を得てしまってもよい。エドガー・ダイクストラが考案したもので、鉄道(車輛)の入れ替えとして説明したことから[1]、操車場という名称がつけられた。初出は、Centrum Wiskunde（オランダ国立数学研究所）のレポート MR 34/61 である（1961年）[2]。
データフローとして見ると、このアルゴリズムには、入力と出力の2つの記号の列（ストリーム）があり、その他に1つ、演算子を保持するスタック（LIFO）として使われる列がある（この3本の列と、それぞれに向かう流れを列車と線路にたとえたわけである）。入力から記号を順次読み出し、その記号とスタックトップの記号に応じて、入力の記号を直接出力に送るか、スタックに積むか、入力を一旦そのままホールドしてスタックトップを取り出して出力に送るか、という動作をする。
操車場アルゴリズムを後に一般化したのが演算子順位構文解析である。
単純な変換例
[編集]
入力: 3+4
- 3 を出力キューに追加する（数値は常に出力にそのまま送られる）。
- + （またはそのID）を演算子スタックにプッシュする。
- 4 を出力キューに追加する。
- 式を読み終わったので、スタックにある演算子群をポップし、出力キューに追加する。この例では "+" だけがスタックにある。
- "3 4 +" が出力となる。
この例で、いくつかの規則が示されている。
- 全ての数値は読み込まれた時点で出力に追加される。
- 式を読み終わったら、スタックから全演算子をポップし、出力に追加していく。
アルゴリズムの詳細
[編集]- 読み込むべきトークンがある間、以下を繰り返す（ここで示すアルゴリズムには、中置記法の演算子の他、atan2(1, 2) といったような（すなわち、前置で括弧と引数セパレータによる引数リストが引き続いている）「関数」の扱いも含まれている）。
- トークンを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>
#include <stdbool.h>
// 演算子
// 優先順位 : 演算子 : 結合性
// 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 == ' ') {
continue;
} else if (is_ident(c)) {
// トークンが数値（識別子）なら、出力キューに追加する
*outpos++ = c;
} else if (is_function(c)) {
// トークンが関数なら、スタックにプッシュする。
stack[sl++] = c;
} else if (c == ',') {
// トークンが関数の引数のセパレータ（例えばカンマ）の場合
bool pe = false;
while (sl > 0) {
sc = stack[sl - 1];
if (sc == '(') {
pe = true;
break;
} else {
// スタックのトップのトークンが左括弧になるまで
// スタック上の演算子を出力キューにポップし続ける
*outpos++ = sc;
sl--;
}
}
// 左括弧が出てこなかった場合、すなわちセパレータの位置が変だった場合
// あるいは括弧が正しく対応していない場合
if (!pe) {
printf("エラー：セパレータか括弧の不一致\n");
return false;
}
} else if (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;
} else if (c == '(') {
// トークンが左括弧なら、スタックにプッシュ
stack[sl++] = c;
} else if (c == ')') {
// トークンが右括弧の場合
bool pe = false;
// スタックのトップにあるトークンが左括弧になるまで
// スタックから出力キューに演算子をポップし続ける
while (sl > 0) {
sc = stack[--sl];
if (sc == '(') {
// スタックから左括弧をポップするが、出力キューには置かない
pe = true;
break;
} else {
*outpos++ = sc;
}
}
// スタックを全部見ても左括弧に到達しなかった場合、左右の括弧の不一致があることになる
if (!pe) {
printf("エラー：括弧の不一致\n");
return false;
}
// スタックのトップにあるトークンが関数トークンなら、それを出力キューにポップする
if (sl > 0) {
sc = stack[sl - 1];
if (is_function(sc)) {
*outpos++ = sc;
sl--;
}
}
} else {
printf("不明なトークン：%c\n", c);
return false; // 不明なトークン
}
}
// 読み込むべきトークンが尽きた際
// スタック上に演算子トークンが残っていたら、それらを出力する
while (sl > 0) {
sc = stack[--sl];
if (sc == '(' || sc == ')') {
printf("エラー：括弧の不一致\n");
return false;
}
*outpos++ = sc;
}
*outpos = 0; // ヌルでターミネート
return true;
}
bool execution_order(const char *input)
{
const char *strpos = input, *strend = input + strlen(input);
char c, res[4];
unsigned int sl = 0, sc, stack[32], rn = 0;
printf("【実行順序】\n");
// 入力トークンがある間ループする
while (strpos < strend) {
// 入力から次のトークンを読み込む
c = *strpos++;
if (is_ident(c)) {
// トークンが値か識別子の場合
// それをスタックにプッシュする。
stack[sl++] = c;
} else if (is_operator(c) || is_function(c)) {
// さもなくば、トークンは演算子である（ここでは関数も演算子に含める）
sprintf(res, "$%d", rn++);
printf("%s = ", res);
// 演算子が n 個の引数をとることは事前にわかっている。
unsigned int nargs = op_arg_count(c);
if (sl < nargs) {
// スタックに n 個未満の値しかない場合
// ユーザーの入力した式に値（引数）が足りないのでエラーを返す
return false;
}
// そうでない場合、スタックから 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++] = *(unsigned int*) res;
}
}
// スタックに1つの値しかない場合、
// その値が計算結果である。
if (sl == 1) {
sc = stack[--sl];
printf("実行結果は %s\n", (char*) &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("【入力】\n%s\n\n", input);
if (shunting_yard(input, output)) {
printf("【出力】\n%s\n\n", output);
if (!execution_order(output)) {
printf("\n不正な入力\n");
}
}
return 0;
}
このコードは次のような結果を出力する。
【入力】 a = D(f - b * c + d, !e, g) 【出力】 afbc*-d+e!gD= 【実行順序】 $0 = b * c; $1 = f - $0; $2 = $1 + d; $3 = ! e; $4 = D($2, $3, g); $5 = a = $4; 実行結果は $5
脚注
[編集]- ^ 日本では近年はほとんど行われなくなったが、旧来の鉄道貨物列車は、まず出発駅から拠点駅に集められ、その後は拠点駅から拠点駅の間を車輛1輛ごとに目的地別に何度か再編成されながら、目的地へ向かう、というものであった。なお余談になるが、考案者のダイクストラには他にも、排他制御機構の「セマフォ」（やはり昔の鉄道で一般的だった腕木式信号機に由来する）など、鉄道関係のたとえが多い。
- ^ 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
オンラインデモ:
実装例: