式の表し方とスタックの応用

結論：このレッスンで覚える4つ

1. 後置表記（逆ポーランド表記）は、演算子を2つの数の後ろに置く書き方です。括弧が要らなくなります。出題数がいちばん多い知識です。
2. 後置表記はスタックで計算します。数が来たら積み、演算子が来たら上から2つ取り出して計算し、結果を積み直します。
3. 3アドレス命令・四つ組は、計算を1ステップずつ並べた形です。上から順に代入していけば元の式に戻せます。
4. 正規表現では、**+ は「1回以上」、* は「0回以上」**の繰返しです。

中置・後置・前置の違い

ふだん使う「a+b」は中置記法（演算子を数の間に置く書き方）です。試験でよく出るのは**後置記法（逆ポーランド記法）**で、同じ式を「ab+」と書きます。

「逆」が付いているほうが後置です。名前を取り違えさせる選択肢に注意しましょう。

用語の確認です。演算子は +、−、×、÷ などの記号、**被演算子（オペランド）**は計算される数や変数（a、b など）のことです。

中置から後置への直し方（いちばん出る）

コツは「最後に計算する演算子を、いちばん後ろに置く」ことです。これを括弧の内側に向かって繰り返します。

手順

1. 式全体で最後に計算される演算子を探す（括弧の外にあり、優先順位がいちばん低いもの。× ÷ は + − より先に計算される）
2. 「[左側の後置] [右側の後置] [その演算子]」の形にする
3. 左側と右側にも同じ手順を当てはめる。変数1文字になったら終わり

式を木の形にすると分かりやすくなります。下の木は (A+B)×(C−D÷E) です。上にあるほど後に計算する演算子です。

flowchart TD
  M["×（最後に計算）"] --> P["+"]
  M --> S["−"]
  P --> A["A"]
  P --> B["B"]
  S --> C["C"]
  S --> V["÷"]
  V --> D["D"]
  V --> E["E"]

この木を「左 → 右 → 自分」の順に読むと AB+CDE÷−× になり、これが後置表記です。

**被演算子（A、B、C…）の並び順は、元の式から変わりません。**選択肢で文字の順番が入れ替わっていたら（ED÷、BA+ など）、その時点で疑いましょう。

後置表記をスタックで計算する

後置表記は左から1文字ずつ読み、次のルールで処理します。

演算子を処理するときは「先に取り出したほうが右側」です。下にあった数（後から取り出す）が左側になります。引き算と割り算では順番を間違えないようにしましょう。

書類トレイに積んだ書類を思い浮かべてください。演算子が来るたびに上の2枚をまとめて1枚にするので、演算子が早く出てくる式ほど、トレイ（スタック）は高く積み上がりません。この性質が「スタックの深さ」の問題で問われます。

なぜ計算にスタックを使うのか

計算の途中結果をいったん積んでおき、別の計算を済ませてから取り出して合わせる、という処理はLIFO（後入れ先出し）の動きそのものです。そのためスタックが向いています。

3アドレス命令・四つ組から式に戻す

3アドレス命令は「c = a op b」のように、被演算子2つと結果1つの合計3つの場所（アドレス）を持つ命令です。四つ組は同じ内容を（演算子, 被演算子1, 被演算子2, 結果）の4つ組で書いたものです。どちらもコンパイラが構文解析（式の構造を読み取ること）をした結果として出てきます。

解き方は、上から順に一時変数を中身で置き換えていくだけです。最後に「括弧を付けないと優先順位が変わってしまう部分」に括弧を付けます。一時変数（T1、w1 など）が残っている選択肢は、式として未完成なので正解にはなりません。

正規表現の + と *（少なめ）

正規表現は、文字列のパターンを記号で表す書き方です。[A−Z] は大文字1文字、[0−9] は数字1文字を表します。

• と * は繰返しの指示です。文字そのものではありません。

試験での問われ方

• 後置への変換（最頻出）：演算子の位置だけ、または被演算子の順番だけをずらした、見た目の似た選択肢が並びます。選択肢をスタックで計算して中置に戻し、問題の式と一致するかを確かめるのが確実です。
• スタックの深さ：「最大の深さが最も少ない式はどれか」と聞かれます。各選択肢でスタックに積まれる個数を数えます。
• 3アドレス命令・四つ組：一時変数が残った式や、括弧が抜けて優先順位が変わった式がひっかけです。
• スタックの用途：キュー（FIFO）の説明や、配列・リストの操作の説明が誤りの選択肢として混ぜられます。
• 正規表現：+ や * を文字として含む文字列や、必須の部分（+ が付いた部分）が欠けた文字列が、誤りの選択肢になります。