式評価

2025年10月21日

式評価

英語表記: Expression Evaluation

概要

式評価（Expression Evaluation）とは、コンピュータが数式や論理式を読み込み、その計算結果の値を得る一連の処理を指します。特に括弧や複数の演算子が混在する複雑な式を扱う際、どの計算を優先すべきか、どの順番で実行すべきかを正確に管理する必要があります。この複雑な順序管理を効率的に行うために、データ構造の「スタック」が主要なツールとして利用されます。スタックは、演算の実行順序を一時的に記憶し、LIFO（後入れ先出し）の特性を用いて計算の優先順位を自動的に制御する、まさに式評価における代表的な用途の一つなのです。

詳細解説

スタックが不可欠な理由

私たちが日常的に使う数式（例: $2 + 3 \times 4$）は「中置記法（Infix Notation）」と呼ばれ、人間には読みやすい形式です。しかし、コンピュータがこの中置記法を直接処理しようとすると、「足し算より掛け算を優先する」といった演算子の優先順位のルールを常に確認しなければならず、非常に非効率です。

ここで、スタックの出番となります。式評価を効率的に行うために、数式はまず「逆ポーランド記法（Reverse Polish Notation / RPN）」、または「後置記法（Postfix Notation）」と呼ばれる形式に変換されます。このRPN形式では、演算子（+ や × など）がオペランド（被演算数、2 や 3 など）の後に配置されるため、括弧を使わずに計算の順序を明確に指定できます。このRPNへの変換プロセス自体も、実はスタック（オペレータースタック）を用いて行われますが、ここでは変換後の評価プロセスに焦点を当てます。

スタックによる評価の仕組み

RPN形式の式をスタックで評価する手順は非常にシンプルでエレガントです。

オペランドのプッシュ: 式を左から右へ読み進めます。数字（オペランド）を見つけたら、すぐにスタックにプッシュ（積み上げ）します。
演算子の処理: 演算子を見つけたら、スタックから直前のオペランドを必要な数だけポップ（取り出し）します。通常、二項演算子であれば2つ取り出します。
計算とプッシュバック: 取り出したオペランドを使って演算を実行し、その計算結果を再びスタックにプッシュします。

このプロセスを式が終了するまで繰り返すと、最終的にスタックに残った一つの値が、その式の最終的な計算結果となります。

LIFO特性の重要性

なぜこの手続きがうまくいくのでしょうか？それは、スタックのLIFO（後入れ先出し）特性が、RPNの性質と完璧にマッチしているからです。RPNでは、ある演算子が出現したとき、その直前に現れたオペランドこそが、その演算子の対象となるべきデータです。スタックは「最も最近プッシュされたデータ」を「最も早くポップできる」ため、計算が必要になった瞬間に必要なオペランドを即座に取り出すことができるのです。

この一連の動作こそが、データ構造（リスト, スタック, キュー, ツリー）という大きな分類の中で、スタックが「式評価」という代表用途を担う決定的な理由です。スタックは一時的な記憶装置として機能し、複雑な優先順位の判断ロジックを必要とせず、機械的に式の評価を進めることを可能にしているのです。

具体例・活用シーン

1. RPN計算機の動作

式評価におけるスタックの役割を最も体感できるのは、RPN対応の電卓です。

例えば、「$2 + 3 \times 4$」という式を考えます。
中置記法で計算すると、先に $3 \times 4 = 12$ を行い、次に $2 + 12 = 14$ となります。
これをRPNに変換すると、「$2 \ 3 \ 4 \ \times \ +$」となります。

スタックを使った評価の様子を見てみましょう。

2 を読み込み $\rightarrow$ スタックに [2] をプッシュ。
3 を読み込み $\rightarrow$ スタックに [2, 3] をプッシュ。
4 を読み込み $\rightarrow$ スタックに [2, 3, 4] をプッシュ。
$\times$ を読み込み $\rightarrow$ 3と4をポップ $\rightarrow$ $3 \times 4 = 12$ を計算 $\rightarrow$ 結果 12 をプッシュ $\rightarrow$ スタックは [2, 12]。
+ を読み込み $\rightarrow$ 2と12をポップ $\rightarrow$ $2 + 12 = 14$ を計算 $\rightarrow$ 結果 14 をプッシュ $\rightarrow$ スタックは [14]。

式評価が終わると、最終結果の14が残ります。このように、スタックは計算の途中結果を保持し、必要なときに正確な順序で取り出すことで、複雑な計算を自動的に解決してくれるのです。

2. コンパイラにおける処理

プログラミング言語のコンパイラやインタープリタは、ソースコード内に記述された複雑な計算式（例: a = (b + c) * (d - e)）を機械語に変換する際に、必ずこの式評価のロジックを使用します。このとき、スタックは一時的なレジスタやメモリの割り当てを管理する上でも非常に重要な役割を果たします。

3. アナロジー：「作業台とレシピのシステム」

式評価におけるスタックの役割を理解するためのアナロジーとして、「特殊な作業台とレシピのシステム」を想像してみてください。

あなたは料理人（CPU）で、目の前には特殊な作業台（スタック）があります。この作業台は、一番上に置いたものしか取り出せない（LIFO）というルールがあります。

オペランド（材料）: 食材（2や3や4）を見つけたら、ただひたすら作業台に積み上げていきます。
演算子（調理指示）: レシピの指示（+ や $\times$）が来たら、あなたは作業台の一番上にある必要な数の食材（直前のオペランド）をサッと取り出し、調理（計算）を行います。
結果: 調理が終わったら、その結果（計算結果）を新しい食材として再び作業台の一番上に置きます。

このシステムでは、複雑なレシピ（式）でも、調理指示（演算子）が来たときに、最も直近で準備された材料（オペランド）を使って処理できるため、「この調理はあの調理より優先だ」といった面倒な判断をする必要がありません。スタック（作業台）が自動的に計算の範囲を限定し、順序を保証してくれるわけです。このシンプルさが、スタックがデータ構造における「代表用途」として式評価に使われる魅力なのです。