操車場アルゴリズム

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