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

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

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

## 単純な変換例

入力: 3+4

1. 3 を出力キューに追加する(数値は常に出力にそのまま送られる)。
2. + (またはそのID)を演算子スタックにプッシュする。
3. 4 を出力キューに追加する。
4. 式を読み終わったので、スタックにある演算子群をポップし、出力キューに追加する。この例では "+" だけがスタックにある。
5. "3 4 +" が出力となる。

この例で、いくつかの規則が示されている。

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

## アルゴリズムの詳細

- 読み込むべきトークンがある間、以下を繰り返す(ここで示すアルゴリズムには、中置記法の演算子の他、atan2(1, 2) といったような(すなわち、前置で括弧と引数セパレータによる引数リストが引き続いている)「関数」の扱いも含まれている)。
  - トークンを1つ読み込む。
  - トークンが数値の場合、それを出力キューに追加する。
  - トークンが関数の場合、それをスタックにプッシュする。
  - トークンが関数の引数セパレータ(カンマなど)の場合
    - スタックのトップにあるトークンが左括弧となるまで、スタックから演算子をポップして出力キューに追加する動作を繰り返す。左括弧が出てこない場合、引数セパレータの位置がおかしいか、左右の括弧が不一致となっている(エラー)。
  - トークンが演算子 o1 の場合
    - スタックのトップに演算子トークン o2 があり、o1 が左結合性で、かつ優先順位が o2 と等しいか低い場合、あるいは、o1 の優先順位が o2 より低い場合、以下を繰り返す。
      - o2 をスタックからポップし、出力キューに追加する。
    - o1 をスタックにプッシュする。
  - トークンが左括弧の場合、スタックにプッシュする。
  - トークンが右括弧の場合
    - スタックのトップにあるトークンが左括弧になるまで、スタックからポップした演算子を出力キューに追加する動作を繰り返す。
    - 左括弧をスタックからポップするが、出力には追加せずに捨てる。
    - スタックのトップにあるトークンが関数トークンなら、それをポップして出力キューに追加する。
    - 左括弧がスタック上に見つからなかった場合、左右の括弧の不一致がある(エラー)。
- 読み込むべきトークンがない場合
  - スタック上に演算子トークンがある間、以下を繰り返す。
    - スタックのトップにある演算子トークンが括弧なら、括弧の不一致がある(エラー)。
    - 演算子をスタックからポップして出力キューに追加する。
- 終了

このアルゴリズムの実行時の複雑性(計算量)の分析にあたり注目すべき点は、各トークンがそれぞれ一度しか読まれず、数値も関数も演算子も一度だけしか出力されず、関数・演算子・括弧はそれぞれ一度スタックにプッシュされ後にポップされるという点である。したがって、トークン毎の操作回数はせいぜい定数値であり、実行時間は O(n)、つまり入力の大きさに比例する。

操車場アルゴリズムは前置記法(ポーランド記法)の生成にも使える。その場合は、入力トークン列を最後尾から先頭に向かって処理し、出力キューを反転させ(つまり、出力キューは出力スタックとなる)、右括弧と左括弧の扱いを反転させればよい(つまり、左括弧については右括弧を見つけるまでスタックをポップし続ける)。

## 詳細な実施例

| トークン | 動作 | 出力 (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言語での実装例

このコードは次のような結果を出力する。