逆ポーランド記法とは？ 集合・形式言語・BNF・オートマトンから体系的に理解する

01｜そもそも何に使うのでしょうか

電卓や表計算ソフトでは、人が入力した「2 + 3 × 4」を正しい順序で計算する必要があります。人は掛け算を優先すると知っていますが、プログラムにはその規則を明示しなければなりません。

逆ポーランド記法（Reverse Polish Notation：RPN）は、演算子を対象の数や変数の後ろへ置く表記法です。後置記法（postfix notation）とも呼びます。例えば通常の「2 + 3」を「2 3 +」と書きます。

人が読む中置記法では、括弧や「掛け算を先に行う」という規則が不可欠です。一方、正しく記述された後置記法では、値を左から読み、演算子が出たときに必要な値を取り出すだけで演算順を再現できます。

02｜中置・前置・後置の3つを比べる

前置記法（ポーランド記法）では演算子を前へ、逆ポーランド記法では後ろへ置きます。いずれも式木の構造と順序が定まれば、通常の二項演算に必要な括弧を省けます。実際の記述では、値がどこで区切られるかを分かるようにします。

03｜演算子の優先順位を式木で理解する

例えば「2 + 3 × 4」は掛け算が先なので 14 です。括弧を付けた「(2 + 3) × 4」は足し算が先なので 20 です。同じ数と演算子でも木の形が変わります。

04｜スタックが必要な理由

スタックは最後に入れた値を最初に取り出すLIFO（Last In, First Out）のデータ構造です。後置記法では、数値ならpush、演算子なら2つをpopして計算結果をpushします。これを末尾まで繰り返します。

05｜逐次計算の表で確認する

最後にスタックに値がただ1つ残れば、完全な二項演算式として評価できたことになります。値が余ったり途中で値が足りなくなったりすれば、不正な入力として検出できます。

06｜中置から後置へ変換する手順

簡単な式なら、優先度が高い部分式を先に後置へ直してから全体を結合できます。一般的な式を機械的に変換するには、演算子専用のスタックを使うシャントヤード法（Shunting-yard algorithm）があります。

1. 数値や変数は出力列へ送ります。
2. 演算子は、先頭にある演算子との優先順位・結合規則を比較してからスタックへ積みます。
3. 開き括弧を積み、閉じ括弧では対応する開き括弧まで演算子を出力する（括弧そのものは出力しません）。
4. 入力の末尾で残った演算子を出力します。

例えば「A + B × C」は、Aを出力、+を保持、Bを出力、×を保持、Cを出力、末尾で×・+の順に出力し「A B C × +」となります。同じ優先順位の二項演算では、左結合か右結合かにも注意が必要です。

07｜TypeScriptで後置式を評価する

function evaluateRpn(tokens: string[]): number {
  const stack: number[] = [];
  for (const token of tokens) {
    if (["+", "-", "*", "/"].includes(token)) {
      if (stack.length < 2) throw new Error("オペランド不足");
      const right = stack.pop()!;
      const left = stack.pop()!;
      if (token === "/" && right === 0) throw new Error("ゼロ除算");
      const result = token === "+" ? left + right
        : token === "-" ? left - right
        : token === "*" ? left * right
        : left / right;
      stack.push(result);
    } else {
      if (!/^-?\d+(?:\.\d+)?$/.test(token))
        throw new Error("不正なトークン");
      stack.push(Number(token));
    }
  }
  if (stack.length !== 1) throw new Error("式が不完全");
  return stack[0];
}
console.log(evaluateRpn(["2", "3", "4", "*", "+"])); // 14

実装例は二項の四則演算と符号付き数値に絞っています。単項マイナス、指数演算、関数呼び出し、任意精度数などを扱うには、トークン定義と演算の規則を拡張する必要があります。

08｜エラーの種類と防御的な設計

外部入力を扱う評価器では、実行時間、式の長さ、スタックの深さ、数値の範囲を制限する必要があります。後置記法だからといって任意のコードを安全に実行できるわけではありません。

09｜電卓や計算アプリの内部では何が起こりますか

「2 + 3 × 4」という入力を、そのまま左から計算すると 20 になってしまいます。正しく 14 を得るには、プログラム側が記号を区切り、文法規則に従って掛け算のまとまりを認識しなければなりません。

大きな流れは字句解析（トークン化）→ 構文解析（文法の確認と構造化）→ 評価です。逆ポーランド記法は、この構造化された式をスタックで扱いやすい列へ表現し直す一つの方法です。BNFを学ぶと、その手前にある「式の正しい形の定義」を理解できます。

補講A｜集合と論理は、形式言語を理解するための土台です

形式言語を学ぶ前に、集合とは「条件を満たすものをまとめたもの」という考え方を押さえておきましょう。例えば、数字の集合を D = {0, 1, 2, …, 9} とします。数字を2個並べた「42」も、数字を3個並べた「314」も、数字を使った記号列です。集合を土台にすると、「ある規則に従う記号列だけを集めたもの」が形式言語だと捉えやすくなります。

ここでは「0が1個以上並び、最後に1が1個続く」などの条件を指定すれば、列の集合を定義できます。集合演算の和集合・共通部分・補集合は複数の条件を組み合わせるために役立ちます。論理のAND・OR・NOTも、字句解析で条件を表したり、状態遷移の受理条件を読んだりするときに登場します。

補講B｜形式言語は『正しい並び方』を指定します

数式を例にすると、使える文字として数字、演算子、括弧があります。しかし、それらを適当に並べても正しい式にはなりません。例えば 2 + 3 は式として読めますが、2 + * 3 は通常の算術文法では認められません。形式文法は、記号をどう並べればよいかを定めます。

BNFやEBNFは、この規則を人にも機械にも読める形で書き表すための記法です。集合は「何が含まれるか」、文法は「どのように生成されるか」という視点を提供します。

補講C｜オートマトンは『その並びを受け付けるか』を調べます

オートマトンは、入力を左から読み取りながら状態を切り替える仕組みです。例えば「数字が1個以上続く」という簡単な規則なら、数字を読んだことがある状態を用意すれば判定できます。有限オートマトンは、正規表現で書けるようなトークンのパターンを扱う際に役立ちます。

DFA（決定性有限オートマトン）では、ある状態である入力を読むと次の状態が一つに決まります。NFA（非決定性有限オートマトン）では、次の状態の候補を複数持てます。どちらも正規言語を認識でき、必要に応じてNFAをDFAへ変換できます。

体験｜文字を1つずつ読み、文法を1行ずつ展開します

「整数のかたまりを見つける仕事」と「数式として並びが正しいか確かめる仕事」を同じ入力で試せます。下のラボでは、123を1文字ずつ読んで受理状態に至る過程と、2 + 3 × 4をBNFの規則に当てはめていく過程を切り替えられます。

<式>   ::= <項> | <式> "+" <項>
<項>   ::= <因子> | <項> "*" <因子>
<因子> ::= 数字 | "(" <式> ")"

補講D｜正規表現・BNF・スタックは役割が違います

これらをすべて「記号を処理する技術」として一括りにすると混乱しやすくなります。トークンを見つける仕事・構造を決める仕事・計算する仕事の三段階に分けると理解しやすいです。ただし実装によっては各段階が統合されることもあります。

補講E｜『符号』は関連していますが、学習目的が異なります

形式言語も符号理論も「記号」を扱いますが、学ぶ目的は同じではありません。形式言語はどの記号列が文法に合うかを扱います。一方、符号理論や符号化では情報をどのようなビット列で表し、どのように効率よく、または誤りに強く伝えるかが中心になります。

符号分野は、文字コード、ハフマン符号、情報量、パリティ、ハミング距離・誤り訂正符号などをまとめて独立したテーマとして学ぶと理解しやすくなります。なお「文字符号化」と「誤り訂正符号」は目的が異なるため、その違いも区別しましょう。

補講F｜体系的な学習マップを整理します

03では全体の接続関係を理解することを目標とします。各分野の理論・証明や詳細なアルゴリズムは、独立した解説で掘り下げると学習の重複を減らせます。

10｜形式言語とは何でしょうか

形式言語は、どの記号列を正しい文として認めるかを規則で定めたものです。自然言語と違い、あいまいさを抑えて機械的に判定できる点が重要です。例えば、四則演算の式では「2 + 3」は正しい構造ですが、「2 + × 3」は通常の文法では認められません。

形式文法は、この許される形を生み出す規則の集まりです。トークン（数字、演算子、括弧など）を並べる規則を定義すると、パーサーが式を読み取れるようになります。

11｜BNFは文法をどう表すのでしょうか

BNF（Backus–Naur Form）は、構文規則を非終端記号・終端記号・生成規則で表す記法です。例えば「式は項、または式に+と項をつなげたもの」といった規則を書けます。

<expr>   ::= <expr> "+" <term> | <expr> "-" <term> | <term>
<term>   ::= <term> "*" <factor> | <term> "/" <factor> | <factor>
<factor> ::= <number> | "(" <expr> ")"
<number> ::= <digit> | <number> <digit>
<digit>  ::= "0" | "1" | ... | "9"

この文法では、expr の内部に term が含まれ、term の内部に factor が含まれています。加減算の規則より深い位置に乗除算を置くことで、掛け算・割り算を1つのまとまりとして解釈できます。

左再帰を含むため、この文法をそのまま単純な再帰下降パーサーに使用すると無限再帰になります。実装方法に応じて文法を変形する必要があります。

実例｜BNFを使って「2 + 3 × 4」を組み立てます

BNFを読み始めるときは、まず小さな文法で練習するのが近道です。次は整数を1桁に限定した、足し算と掛け算の文法です。山括弧付きの名前は「これから展開する部品」、引用符の中は「実際に入力へ現れる文字」です。

<式> ::= <項> | <式> "+" <項>
<項> ::= <数> | <項> "×" <数>
<数> ::= "2" | "3" | "4"

ここで重要なのは、「2 + 3 × 4」という文字列を作れることと、掛け算が右側の項としてひとまとまりになることです。構文解析は、このような構造を入力から逆向きに特定する作業だと考えられます。

12｜EBNFを使うと繰り返しを簡潔に書けます

EBNF（Extended BNF）は、BNFを拡張して繰り返しや任意の要素を表しやすくした記法です。ただし、記号の使い方は規格やツールごとに異なるため、文法を読む際はその記法の定義を確認します。

(* ISO/IEC 14977に近い書き方の例 *)
expression = term, { ("+" | "-"), term } ;
term       = factor, { ("*" | "/"), factor } ;
factor     = number | "(", expression, ")" ;
number     = digit, { digit } ;
digit      = "0" | "1" | "2" | "3" | "4"
           | "5" | "6" | "7" | "8" | "9" ;

この例では、{ ... } が0回以上の繰り返し、カンマが連結、縦棒が選択を表します。例えば expression は「最初の項の後ろに、+または−と項の組が何度でも続く形」です。実装ではこの構造をループに落とし込みやすくなります。

13｜構文木と抽象構文木はどう違うのでしょうか

具体的な構文木（parse tree）は、文法規則の展開を詳しく保持します。一方、抽象構文木（AST：Abstract Syntax Tree）は、処理に必要な意味構造へ整理します。例えば「2 + 3 × 4」のASTは、根が加算、その右子が乗算、乗算の子が3と4です。

ASTを左の子 → 右の子 → 親の順で後順走査すると、「2 3 4 × +」が得られます。つまり、後置記法はASTの走査結果と直接対応しています。一方、前順走査なら「+ 2 × 3 4」となります。

14｜構文解析と後置式への変換は別の仕事です

構文解析は文法に従って入力の構造を確定する処理です。シャントヤード法は演算子の優先順位や括弧を扱いながら中置記法を後置記法へ変換できますが、すべての言語の構文を解析する方法ではありません。

複雑なプログラミング言語では、字句解析器やパーサーがASTを生成し、その後に意味解析や中間表現への変換などの処理を行います。RPNは「式の構造を評価可能な列へ並べる」という役割を理解する入口として役立ちます。

15｜文法の種類と正規表現との関係も整理します

形式言語には、正規言語、文脈自由言語などの分類があります。一般に字句解析で扱う識別子や整数のようなトークンは正規表現で記述しやすく、括弧が入れ子になる式の構造には文脈自由文法が適しています。

例えば「( ( 2 + 3 ) × 4 )」のような括弧の対応を任意の深さまで扱うには、通常の有限オートマトンだけでは足りません。スタックを持つプッシュダウンオートマトンが、文脈自由言語と深く関係します。逆ポーランド記法の評価でもスタックを使いますが、これは構文の認識と式の計算という異なる目的で使われています。

16｜関連知識を効率よく学ぶ順番

1. 数式の優先順位：掛け算と括弧で評価順序が変わることを確認します。
2. スタック：push・popと、二項演算で右の値を先に取り出すことを学びます。
3. BNF・EBNF：式として許される形を明示する方法を読みます。
4. 字句解析・構文解析：文字をトークンに分け、その構造を決める流れを追います。
5. ASTとRPN：ASTの後順走査が後置表記につながることを確認します。
6. 実装：スタックで評価し、次に優先順位を考慮した変換を実装します。

最初から形式文法の全分類を暗記するより、一つの式が処理される様子を軸に概念をつなげるほうが理解しやすくなります。

17｜実際の利用場面

RPNは電卓の操作体系、式のコンパイル、仮想マシンのスタック型命令列などを理解する入口になります。ただし現代のコンパイラは抽象構文木（AST）や中間表現（IR）など多様な表現を使用するため、「すべての処理系がRPNに変換する」というわけではありません。

式木を後順走査すると後置表記が得られます。この関係は式のパース、構文解析、木の走査アルゴリズムを学ぶときにも役立ちます。

18｜操作ラボ：1トークンずつ計算する

スタック内の値を見ながら、「次へ」でトークンを1つ処理できます。掛け算の優先順位、括弧の違い、引き算の順序、オペランド不足によるエラーを体験してみましょう。

19｜理解度チェック

20｜まとめ

逆ポーランド記法は演算子を値の後ろに置く表記法であり、スタックを使えば左から順に評価できます。重要なのは「優先順位の結果がトークン列に埋め込まれること」「二項演算では右の値を先にpopすること」「終了時のスタック検査」の3点です。さらにBNFが式の文法を定義し、構文解析がASTを構築し、後順走査でRPNが得られるという関係を理解すると、数式処理を体系的に捉えられます。

参考資料

• Reverse Polish notation — Encyclopaedia Britannica
• Parsing Expressions by Recursive Descent — Theodore Norvell
• Data Structures and Algorithms in Java (stack overview) — Oracle