逆ポーランド記法とは
逆ポーランド記法（ぎゃくぽーらんどきほう）とは、数式を書くときに、演算子（＋やーなどの記号）を数値の「後ろ」に配置する書き方のことです。「後置記法」とも呼ばれます。私たちが普段使っている「3 ＋ 4」のような書き方は「中置記法」と呼ばれ、演算子が数値の間にあります。これに対して逆ポーランド記法では「3 4 ＋」と書きます。この書き方の最大のメリットは、カッコ「（ ）」を使わなくても計算の優先順位を一切曖昧にすることなく表現できる点です。コンピュータのメモリ管理構造の1つである「スタック」と非常に相性が良く、コンピュータが数式を左から順に読み込んで高速かつシンプルに計算処理を行うために最適化された記法です。
具体例
カッコを使った少し複雑な式「 (1 ＋ 2) × 4 」を、逆ポーランド記法に変換してみましょう。
通常の数式： (1 ＋ 2) × 4
逆ポーランド記法： 1 2 ＋ 4 ×
【コンピュータの計算手順】
1. 左から順に数字の「1」と「2」を一時保管（スタックに積む）します。
2. 次の「＋」を読み込んだら、保管してある「1」と「2」を足して「3」にします。
3. 次の数字「4」を一時保管します。
4. 最後の「×」を読み込んだら、「3」と「4」を掛けて、答えの「12」を得ます。もう少し詳しく
逆ポーランド記法（Reverse Polish Notation, RPN）は、1920年代にポーランドの論理学者ヤン・ウカシェヴィチによって考案された「ポーランド記法（前置記法：＋ 3 4）」を逆順にしたものです。コンピュータにとって、通常の数式（中置記法）は「掛け算を足し算より先に計算する」「カッコの中を最優先にする」といった複雑な先読み処理が必要になるため、計算アルゴリズムが複雑になります。しかし逆ポーランド記法を使えば、「LIFO（後入れ先出し）」の特徴を持つスタックというデータ構造を使うだけで、左から右へ1回読むだけで一切の迷いなく計算を完了できます。数値を読み込んだらスタックに『Push（積む）』し、演算子を読み込んだらスタックから数値を2つ『Pop（取り出す）』して計算し、結果を再び『Push』する、という極めて単純で機械的な処理の繰り返しで、どんなに複雑な数式でも解くことができる美しい仕組みです。
試験でのポイント
基本情報技術者試験では、逆ポーランド記法に関する計算問題や変換問題が非常によく出題されます。「A B ＋ C × を通常の式に直すとどれか（答え：(A＋B)×C）」といった変換問題や、二分木（構文木）で表された数式を「後行がけ（左の子→右の子→親の順）」でたどって逆ポーランド記法を生成する問題が代表的です。また、「逆ポーランド記法を実行するためのデータ構造はどれか」という知識問題の答えが「スタック」になることも超頻出事項です。手作業で変換する場合は、「計算を先に実行したい部分のすぐ後ろに演算子を移動させる」というルールを意識するとミスを防ぐことができます。
関連する用語
逆ポーランド記法の計算アルゴリズムに不可欠なデータ構造であるスタック、データを取り出す操作であるポップ（Pop）、データを格納する操作であるプッシュ（Push）などが関連します。