Loading article…
コンピュータサイエンスにおいて、シャンティングヤードアルゴリズムは、中置記法で指定された算術式または論理式、あるいはその両方の組み合わせを解析する方法です。これは、逆ポーランド記法（RPN）としても知られる後置記法文字列、または抽象構文木（AST）のいずれかを生成できます。[ 1 ]このアルゴリズムは、エドガー・ダイクストラによって考案され、1961年11月に初めて発表されました。[ 2 ]その動作が鉄道のシャンティングヤードの動作に似ていることから、この名前が付けられました。
RPN の評価と同様に、シャントヤード アルゴリズムもスタックベースです。中置記法は、多くの人が慣れ親しんでいる数学表記の形式で、たとえば「3 + 4」や「3 + 4 × (2 − 1)」などです。変換には、入力と出力の2 つのテキスト変数(文字列) があります。出力キューにまだ追加されていない演算子を保持するスタックもあります。変換するには、プログラムは各シンボルを順番に読み込み、そのシンボルに基づいて何らかの処理を行います。上記の例の結果は、(逆ポーランド記法で)それぞれ「3 4 +」と「3 4 2 1 − × +」になります。
シャントヤードアルゴリズムは、有効な中置記法式をすべて正しく解析しますが、無効な式をすべて拒否するわけではありません。たとえば、「1 2 +」は有効な中置記法式ではありませんが、 「1 + 2」と解析されます。ただし、このアルゴリズムは、括弧の対応が一致しない式を拒否することができます。
入換ヤードアルゴリズムは後に演算子優先順位解析へと一般化された。
これは既にいくつかのルールを示しています。
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 をプッシュする - "," : 演算子スタックの最上位の演算子が左括弧でない場合: オペレータースタックからオペレーターをポップして出力キューに入れる -左括弧（例：「（）」）： それを演算子スタックにプッシュする -右括弧(つまり ")"): 演算子スタックの最上位の演算子が左括弧でない場合: { assert the operator stack is not empty} /* 左括弧が見つからずにスタックが尽きた場合、括弧の不一致があります。 */ オペレータースタックからオペレーターをポップして出力キューに入れる演算子スタックの最上位に左括弧が存在することを アサートする。 演算子スタックから左括弧をポップして破棄する 演算子スタックの最上位に関数トークンがある場合： 演算子スタックから関数をポップして出力キューに格納する /* whileループの後、演算子スタックから残りの項目を出力キューにポップします。 */ 演算子スタックにトークンがある 間: /* スタックの最上位にある演算子トークンが括弧の場合、括弧の不一致があります。 */ {スタックの最上位にある演算子が（左）括弧ではないことをアサートします} オペレータースタックからオペレーターをポップして出力キューに送る
このアルゴリズムの実行時間複雑度を分析するには、各トークンが一度読み込まれ、各数値、関数、または演算子が一度出力され、各関数、演算子、または括弧が一度スタックにプッシュされ、スタックからポップされることに注目するだけでよい。したがって、トークンごとに実行される操作は最大で定数個であり、実行時間は入力のサイズに対して線形である O( n ) となる。
シャントヤードアルゴリズムは、プレフィックス表記（ポーランド記法とも呼ばれる）を生成するためにも適用できます。これを行うには、解析するトークンの文字列の末尾から始めて逆方向に処理し、出力キューを反転させ（したがって出力キューを出力スタックにする）、左括弧と右括弧の動作を反転させ（左括弧の動作は右括弧が見つかるまでポップする必要があることを覚えておく）、結合条件を右に変更します。
入力: 3 + 4 × 2 ÷ ( 1 − 5 ) ^ 2 ^ 3
記号 ^ はべき乗演算子を表します。
入力: sin ( max ( 2, 3 ) ÷ 3 × π )