操車場アルゴリズム
入力: 3+4
3 を出力キューに追加する(数値は常に出力にそのまま送られる)。
+ (またはそのID)を演算子スタックにプッシュする。
4 を出力キューに追加する。
式を読み終わったので、スタックにある演算子群をポップし、出力キューに追加する。この例では "+" だけがスタックにある。
"3 4 +" が出力となる。
この例で、いくつかの規則が示されている。
全ての数値は読み込まれた時点で出力に追加される。
式を読み終わったら、スタックから全演算子をポップし、出力に追加していく。
左括弧をスタックからポップするが、出力には追加せずに捨てる。 スタックのトップにあるトークンが関数トークンなら、それをポップして出力キューに追加する。 左括弧がスタック上に見つからなかった場合、左右の括弧の不一致がある(エラー)。
読み込むべきトークンがない場合 スタック上に演算子トークンがある間、以下を繰り返す。 スタックのトップにある演算子トークンが括弧なら、括弧の不一致がある(エラー)。 演算子をスタックからポップして出力キューに追加する。
終了
このアルゴリズムの実行時の複雑性(計算量)の分析にあたり注目すべき点は、各トークンがそれぞれ一度しか読まれず、数値も関数も演算子も一度だけしか出力されず、関数・演算子・括弧はそれぞれ一度スタックにプッシュされ後にポップされるという点である。したがって、トークン毎の操作回数はせいぜい定数値であり、実行時間は O(n)、つまり入力の大きさに比例する。
操車場アルゴリズムは前置記法(ポーランド記法)の生成にも使える。その場合は、入力トークン列を最後尾から先頭に向かって処理し、出力キューを反転させ(つまり、出力キューは出力スタックとなる)、右括弧と左括弧の扱いを反転させればよい(つまり、左括弧については右括弧を見つけるまでスタックをポップし続ける)。