式評価と構文解析
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/09 23:01 UTC 版)
逆ポーランド記法を使用している電卓（Hewlett-Packardの関数電卓など）は、値を保持するためにスタック構造を使う。式は、前置記法、中置記法、後置記法のいずれかで表現される。ある記法から別の記法への変換にはスタックが必要となる。多くのコンパイラは低レベルな言語に翻訳する前の構文解析のためにスタックを使用する。多くのプログラミング言語は文脈自由言語であり、スタックベースの機械で構文解析することができる。ちなみに自然言語は文脈依存言語であり、スタックだけではその意味を解釈することはできない。 例えば、((1 + 2) * 4) + 3 という計算は、交換法則と括弧を優先するという前提で、次のように後置記法（逆ポーランド記法）に変換できる。 1 2 + 4 * 3 + この式はスタックを使って左から右に以下のように評価できる。 オペランド（演算数）に遭遇したら push する。 演算子に遭遇したら、スタックから2つのオペランドを pop して演算を行い、 その解を push する。 具体的には以下のようになる。「スタック」は「操作」した後の状態を示している。 入力操作スタック1 オペランドをPush 1 2 オペランドをPush 1, 2 + 加算 3 4 オペランドをPush 3, 4 * 乗算 12 3 オペランドをPush 12, 3 + 加算 15 最終的な演算結果は 15 で、終了時にスタックのトップに置かれている。
※この「式評価と構文解析」の解説は、「スタック」の解説の一部です。
「式評価と構文解析」を含む「スタック」の記事については、「スタック」の概要を参照ください。
- 式評価と構文解析のページへのリンク
