詳細な実施例とは？ わかりやすく解説

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/02/20 09:34 UTC 版)

「操車場アルゴリズム」の記事における「詳細な実施例」の解説

入力: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3演算子優先順位結合性^ 4 右 * 3 左 / 3 左 + 2 左 - 2 左 トークン動作出力 (RPN)演算子スタック備考3 トークンを出力に追加 3 + トークンをスタックにプッシュ 3 + 4 トークンを出力に追加 3 4 + * トークンをスタックにプッシュ 3 4 * + * は ＋ より優先順位が高い 2 トークンを出力に追加 3 4 2 * + / スタックからポップして出力へ 3 4 2 * + / と * の優先順位は同じ トークンをスタックにプッシュ 3 4 2 * / + / は ＋ より優先順位が高い ( トークンをスタックにプッシュ 3 4 2 * ( / + 1 トークンを出力に追加 3 4 2 * 1 ( / + − トークンをスタックにプッシュ 3 4 2 * 1 − ( / + 5 トークンを出力に追加 3 4 2 * 1 5 − ( / + ) スタックからポップして出力へ 3 4 2 * 1 5 − ( / + "(" が見つかるまで繰り返す スタックからポップ 3 4 2 * 1 5 − / + マッチした括弧を捨てる ^ トークンをスタックにプッシュ 3 4 2 * 1 5 − ^ / + ^ は / より優先順位が高い 2 トークンを出力に追加 3 4 2 * 1 5 − 2 ^ / + ^ トークンをスタックにプッシュ 3 4 2 * 1 5 − 2 ^ ^ / + ^ は右結合性 3 トークンを出力に追加 3 4 2 * 1 5 − 2 3 ^ ^ / + end スタックから出力へ全部をポップ 3 4 2 * 1 5 − 2 3 ^ ^ / + 中置記法からRPNへの変換は、数式を簡単に単純化するのにも使える。そのためにはRPNの式を評価するようにし、値がヌルの変数が出てきたり、値がヌルの演算子が出てきたら、そのパラメータと共に出力に書き込めばよい（これは単純化であり、パラメータが別の演算子だった場合には問題が生じる）。ヌルのパラメータがない演算子の場合は、単にその値を出力に書き込めばよい。この技法は明らかにあらゆる単純化を含んでいるわけではない。それは定数畳み込みの最適化に近い。

※この「詳細な実施例」の解説は、「操車場アルゴリズム」の解説の一部です。
「詳細な実施例」を含む「操車場アルゴリズム」の記事については、「操車場アルゴリズム」の概要を参照ください。