操車場アルゴリズム

操車場アルゴリズム（そうしゃじょうあるごりずむ）は、計算機科学において、中置記法の数式を構文解析する技法である。逆ポーランド記法 (RPN) または抽象構文木 (AST) の形式で出力を生成するのに使える。このアルゴリズムはエドガー・ダイクストラが考案したもので、スタックの操作をデルタ線を使用した車両の入れ替えとして説明したことから、操車場という名称がつけられた。ダイクストラが操車場アルゴリズムを最初に発表したのは、Centrum Wiskunde（オランダ国立数学研究所）のレポート MR 34/61 である（1961年）。RPNの評価技法と同様、操車場アルゴリズムはスタックに基づいている。中置記法の数式は最も一般的な数学的記法であり、例えば 3+4 や 3+4*(2−1) がそうである。変換に際して、入力用と出力用の2つのテキスト変数（文字列）を使用する。他に出力キューに追加する前の演算子を保持するスタックが必要である。入力文字列からシンボル（トークン）を順次読み出し、その後もシンボル単位で処理を行う。操車場アルゴリズムを後に一般化したのがである。