操車場アルゴリズム

操車場アルゴリズム（そうしゃじょうアルゴリズム）は、なんらかの中置記法に属する構文に従った順序で記号（トークン）が並んでいる、数式等の記号列を解析（構文解析）する、スタックベースのアルゴリズムである。その出力を出力順にそのまま並べれば逆ポーランド記法 (RPN) になるし、あるいは抽象構文木を構築したり、数値と四則演算等の算術式のようなものであればその場で直接計算結果を得てしまってもよい。エドガー・ダイクストラが考案したもので、鉄道(車輛)の入れ替えとして説明したことから、操車場という名称がつけられた。初出は、Centrum Wiskunde（オランダ国立数学研究所）のレポート MR 34/61 である（1961年）。
データフローとして見ると、このアルゴリズムには、入力と出力の2つの記号の列（ストリーム）があり、その他に1つ、演算子を保持するスタック（LIFO）として使われる列がある（この3本の列と、それぞれに向かう流れを列車と線路にたとえたわけである）。入力から記号を順次読み出し、その記号とスタックトップの記号に応じて、入力の記号を直接出力に送るか、スタックに積むか、入力を一旦そのままホールドしてスタックトップを取り出して出力に送るか、という動作をする。
操車場アルゴリズムを後に一般化したのが演算子順位構文解析である。

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