操車場アルゴリズム

操車場アルゴリズム

クラス	解析
データ構造	スタック
最悪の場合の パフォーマンス	${\displaystyle O(n)}$
最悪の場合の 空間複雑度	${\displaystyle O(n)}$

コンピュータサイエンスにおいて、操車場アルゴリズムは、中置記法で指定された算術式または論理式、またはその両方の組み合わせを解析する方法です。これは、逆ポーランド記法(RPN)とも呼ばれる後置記法文字列、または抽象構文木(AST) のいずれかを生成できます。^[1]このアルゴリズムは、エドガー・ダイクストラによって発明され、1961 年 11 月に初めて公開されました。^{[2]その動作が}鉄道の操車場の動作に似ていることから、「操車場」アルゴリズムと名付けられました。

RPN の評価と同様に、操車場アルゴリズムはスタックベースです。インフィックス式は、ほとんどの人が慣れている数学表記の形式で、たとえば「3 + 4」や「3 + 4 × (2 − 1)」などです。変換には、入力と出力の2 つのテキスト変数(文字列) があります。また、出力キューにまだ追加されていない演算子を保持するスタックもあります。変換するには、プログラムは各シンボルを順番に読み取り、そのシンボルに基づいて何かを行います。上記の例の結果は、それぞれ (逆ポーランド記法では) 「3 4 +」と「3 4 2 1 − × +」になります。

操車場アルゴリズムは、すべての有効なインフィックス式を正しく解析しますが、すべての無効な式を拒否するわけではありません。たとえば、「1 2 +」は有効なインフィックス式ではありませんが、 「1 + 2」として解析されます。ただし、アルゴリズムは括弧が一致しない式を拒否できます。

操車場アルゴリズムは後に演算子優先順位解析に一般化されました。

1. 入力: 3 + 4
2. 3 を出力キューにプッシュします(数字が読み取られるたびに出力にプッシュされます)
3. + (またはそのID)を演算子スタックにプッシュします
4. 出力キューに4をプッシュする
5. 式を読み取った後、演算子をスタックから ポップし、出力に追加します。

   この場合、「+」は 1 つだけです。

6. 出力: 3 4 +

これにはすでにいくつかのルールが示されています:

• すべての数字は読み取られると出力にプッシュされます。
• 式の読み取りの最後に、すべての演算子をスタックからポップして出力します。

3 方向の鉄道ジャンクションを使用したアルゴリズムのグラフィカルな説明。入力は一度に 1 つのシンボルずつ処理されます。変数または数値が見つかった場合は、出力に直接コピーされます (a)、c)、e)、h)。シンボルが演算子の場合は、演算子スタックにプッシュされます (b)、d)、f)。演算子の優先順位がスタックの一番上の演算子よりも低い場合、または優先順位が等しく演算子が左結合である場合、その演算子はスタックからポップされ、出力に追加されます (g)。最後に、残りの演算子がスタックからポップされ、出力に追加されます (i)。

/* このアルゴリズムで参照される関数は、正弦関数、逆関数、階乗関数などの単純な単一引数関数です。 */ 
/* この実装では、複合関数、可変数の引数を持つ関数、または単項演算子は実装されていません。 */

読み取るトークンがある間:
    トークンを読む
    トークンが次の場合:
    -数字:
        出力キューに入れる
    -関数:
        それをオペレータスタックにプッシュする
    -演算子 o 1 :
         while (演算子スタックの先頭に左括弧ではない 
            
            演算子o 2があり、 ( o 2 はo 1よりも優先順位が高いか、 ( o 1とo 2 は同じ優先順位を持ち、o 1は左結合です))  
        ):演算子スタックから出力キューにo 2 を
            ポップするo 1を演算子スタックに
        プッシュする
    - "," :
        演算子スタックの先頭の演算子が左括弧ではない場合:
             演算子を演算子スタックから出力キューにポップする
    -左括弧（つまり「(」）：
        それをオペレータスタックにプッシュする
    -右括弧(つまり ")"):
        演算子スタックの先頭の演算子は左括弧ではありません。
            {演算子スタックが空でないこと
            をアサートします} /* 左括弧が見つからないままスタックがなくなる場合は、括弧が一致していません。 */
            演算子を演算子スタックから出力キューにポップする
        {演算子スタックの先頭に左括弧があることを確認します}
        左括弧を演算子スタックからポップして破棄する
        演算子スタックの先頭に関数トークンがある場合、次のようになります。
            関数を演算子スタックから出力キューにポップする
/* while ループの後、演算子スタックの残りの項目を出力キューにポップします。 */ 
while演算子スタックにトークンがある場合:
     /* スタックの一番上の演算子トークンが括弧の場合、括弧が一致しません。 */ 
    {スタックの一番上の演算子が (左) 括弧ではないことを確認します}
    演算子を演算子スタックから出力キューにポップする

このアルゴリズムの実行時間の複雑さを分析するには、各トークンが 1 回読み取られ、各数値、関数、または演算子が 1 回印刷され、各関数、演算子、または括弧がスタックにプッシュされ、スタックから 1 回ポップされることに注目するだけで済みます。したがって、トークンごとに実行される操作の数は最大で一定数であり、実行時間は O( n ) であり、入力のサイズに比例します。

操車場アルゴリズムは、プレフィックス表記法 (ポーランド表記法とも呼ばれる) の生成にも適用できます。これを行うには、解析するトークンの文字列の末尾から開始して逆方向に作業し、出力キューを反転し (したがって、出力キューを出力スタックにします)、左括弧と右括弧の動作を反転します (左括弧の動作は、右括弧が見つかるまでポップする必要があることに注意してください)。そして、結合条件を右に変更します。

入力: 3 + 4 × 2 ÷ ( 1 − 5 ) ^ 2 ^ 3

記号 ^ は累乗演算子を表します。

入力: sin ( max ( 2, 3 ) ÷ 3 × π )

• 演算子優先順位パーサー
• スタックソート可能な順列

• ダイクストラによる操車場アルゴリズムのオリジナルの説明
• C言語による文芸プログラムの実装
• Rust での操車場アルゴリズムのデモンストレーション
• 操車場アルゴリズムを示す Java アプレット
• 操車場アルゴリズムと算術式の評価を示す Silverlight ウィジェット
• 再帰的降下による式の解析 Theodore Norvell © 1999–2001。アクセス日 2006 年 9 月 14 日。
• Matlab コード、操車場アルゴリズムを使用した算術式の評価