操車場アルゴリズム(そうしゃじょうアルゴリズム)は、なんらかの中置記法に属する構文に従った順序で記号(トークン)が並んでいる、数式等の記号列を解析(構文解析)する、スタックベースのアルゴリズムである。なるし、あるいは抽象構文木を構築したり、数値と四則演算等の算術式のようなものであればその場で直接計算結果を得てしまってもよい。エドガー・ダイクストラが考案したもので、鉄道(車輛)の入れ替えとして説明したことから[1]、操車場という名称がつけられた。ある(1961年)[2]。データフローとして見ると、このアルゴリズムには、入力と出力の2つの記号の列(ストリーム)があり、その他に1つ、演算子を保持するスタック(LIFO)として使われる列がある(この3本の列と、それぞれに向かう流れを列車と線路にたとえたわけである)。入力から記号を順次読み出し、その記号とスタックトップの記号に応じて、入力の記号を直接出力に送るか、スタックに積むか、入力を一旦そのままホールドしてスタックトップを取り出して出力に送るか、という動作をする。外部リンク単純な変換例[編集]このアルゴリズムを3方向の線路で視覚的に表した図。入力は一度に1シンボルずつ処理され、変数や数値は直接、出力にコピーする。演算子は演算子スタックにプッシュするが、スタックのトップにある演算子よりも優先順位が低い場合や、演算子が左結合性でスタックのトップにある演算子と同じか低い優先順位なら、スタックのトップにある演算子をポップして出力に加える。最後に残った演算子をポップして出力に加える。出力キューに追加する(数値は常に出力にそのまま送られる)。(またはそのID)を演算子スタックにプッシュする。出力キューに追加する。式を読み終わったので、スタックにある演算子群をポップし、出力キューに追加する。