操車場アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/02/20 09:34 UTC 版)
操車場アルゴリズム（そうしゃじょうアルゴリズム）は、なんらかの中置記法に属する構文に従った順序で記号（トークン）が並んでいる、数式等の記号列を解析（構文解析）する、スタックベースのアルゴリズムである。その出力を出力順にそのまま並べれば逆ポーランド記法 (RPN) になるし、あるいは抽象構文木を構築したり、数値と四則演算等の算術式のようなものであればその場で直接計算結果を得てしまってもよい。エドガー・ダイクストラが考案したもので、鉄道(車輛)の入れ替えとして説明したことから[1]、操車場という名称がつけられた。初出は、Centrum Wiskunde（オランダ国立数学研究所）のレポート MR 34/61 である（1961年）[2]。
- ^ 日本では近年はほとんど行われなくなったが、旧来の鉄道貨物列車は、まず出発駅から拠点駅に集められ、その後は拠点駅から拠点駅の間を車輛1輛ごとに目的地別に何度か再編成されながら、目的地へ向かう、というものであった。なお余談になるが、考案者のダイクストラには他にも、排他制御機構の「セマフォ」（やはり昔の鉄道で一般的だった腕木式信号機に由来する）など、鉄道関係のたとえが多い。
- ^ Dijkstra, E.W. (1961). Algol 60 translation : An algol 60 translator for the x1 and making a translator for algol 60. Stichting Mathematisch Centrum.
[続きの解説]
「操車場アルゴリズム」の続きの解説一覧
- 1 操車場アルゴリズムとは
- 2 操車場アルゴリズムの概要
- 3 C言語での実装例
- 4 外部リンク
- 操車場アルゴリズムのページへのリンク
