アルゴリズムの詳細
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/02/20 09:34 UTC 版)
「操車場アルゴリズム」の記事における「アルゴリズムの詳細」の解説
読み込むべきトークンがある間、以下を繰り返す（ここで示すアルゴリズムには、中置記法の演算子の他、atan2(1, 2) といったような（すなわち、前置で括弧と引数セパレータによる引数リストが引き続いている）「関数」の扱いも含まれている）。トークンを1つ読み込む。 トークンが数値の場合、それを出力キューに追加する。 トークンが関数の場合、それをスタックにプッシュする。 トークンが関数の引数セパレータ（カンマなど）の場合スタックのトップにあるトークンが左括弧となるまで、スタックから演算子をポップして出力キューに追加する動作を繰り返す。左括弧が出てこない場合、引数セパレータの位置がおかしいか、左右の括弧が不一致となっている（エラー）。 トークンが演算子 o1 の場合スタックのトップに演算子トークン o2 があり、o1 が左結合性（英語版）で、かつ優先順位が o2 と等しいか低い場合、あるいは、o1 の優先順位が o2 より低い場合、以下を繰り返す。o2 をスタックからポップし、出力キューに追加する。 o1 をスタックにプッシュする。 トークンが左括弧の場合、スタックにプッシュする。 トークンが右括弧の場合スタックのトップにあるトークンが左括弧になるまで、スタックからポップした演算子を出力キューに追加する動作を繰り返す。 左括弧をスタックからポップするが、出力には追加せずに捨てる。 スタックのトップにあるトークンが関数トークンなら、それをポップして出力キューに追加する。 左括弧がスタック上に見つからなかった場合、左右の括弧の不一致がある（エラー）。 読み込むべきトークンがない場合スタック上に演算子トークンがある間、以下を繰り返す。スタックのトップにある演算子トークンが括弧なら、括弧の不一致がある（エラー）。 演算子をスタックからポップして出力キューに追加する。 終了 このアルゴリズムの実行時の複雑性（計算量）の分析にあたり注目すべき点は、各トークンがそれぞれ一度しか読まれず、数値も関数も演算子も一度だけしか出力されず、関数・演算子・括弧はそれぞれ一度スタックにプッシュされ後にポップされるという点である。したがって、トークン毎の操作回数はせいぜい定数値であり、実行時間は O(n)、つまり入力の大きさに比例する。 操車場アルゴリズムは前置記法（ポーランド記法）の生成にも使える。その場合は、入力トークン列を最後尾から先頭に向かって処理し、出力キューを反転させ（つまり、出力キューは出力スタックとなる）、右括弧と左括弧の扱いを反転させればよい（つまり、左括弧については右括弧を見つけるまでスタックをポップし続ける）。
※この「アルゴリズムの詳細」の解説は、「操車場アルゴリズム」の解説の一部です。
「アルゴリズムの詳細」を含む「操車場アルゴリズム」の記事については、「操車場アルゴリズム」の概要を参照ください。
- アルゴリズムの詳細のページへのリンク
