|
操車場アルゴリズム（そうしゃじょうあるごりずむ）は、計算機科学において、中置記法の数式を構文解析する技法である。逆ポーランド記法 (RPN) または抽象構文木 (AST) の形式で出力を生成するのに使える。このアルゴリズムはエドガー・ダイクストラが考案したもので、スタックの操作をデルタ線を使用した車両の入れ替えとして説明したことから、操車場という名称がつけられた。ダイクストラが操車場アルゴリズムを最初に発表したのは、Centrum Wiskunde（オランダ国立数学研究所）のレポート MR 34/61 である（1961年）。 RPNの評価技法と同様、操車場アルゴリズムはスタックに基づいている。中置記法の数式は最も一般的な数学的記法であり、例えば 3+4 や 3+4 *(2−1) がそうである。変換に際して、入力用と出力用の2つのテキスト変数（文字列）を使用する。他に出力キューに追加する前の演算子を保持するスタックが必要である。入力文字列からシンボル（トークン）を順次読み出し、その後もシンボル単位で処理を行う。 操車場アルゴリズムを後に一般化したのがである。 == 単純な変換例 == :入力: 3+4 # 3 を出力キューに追加する（数値は常に出力にそのまま送られる）。 # + （またはそのID）を演算子スタックにプッシュする。 # 4 を出力キューに追加する。 # 式を読み終わったので、スタックにある演算子群をポップし、出力キューに追加する。この例では "+" だけがスタックにある。 # "3 4 +" が出力となる。 この例で、いくつかの規則が示されている。 * 全ての数値は読み込まれた時点で出力に追加される。 * 式を読み終わったら、スタックから全演算子をポップし、出力に追加していく。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「操車場アルゴリズム」の詳細全文を読む スポンサード リンク
|