逆ポーランド記法 (ぎゃくポーランドきほう) とは | 意味や読み方など丁寧でわかりやすい用語解説

逆ポーランド記法 (ぎゃくポーランドきほう) の読み方

日本語表記

ぎゃくポーランドきほう (ギャクポーランドキホウ)

英語表記

Reverse Polish notation (リバースポーランド記法)

逆ポーランド記法 (ぎゃくポーランドきほう) の意味や用語解説

逆ポーランド記法は、数式を表現するための一つの方法であり、後置記法とも呼ばれる。その最大の特徴は、演算子を計算対象となる二つ以上の数値の後に記述する点にある。例えば、私たちが日常的に使用する「1 + 2」という表記法は、演算子を数値の間に置くため中置記法と呼ばれる。これを逆ポーランド記法で表すと「1 2 +」となる。この記法の本質的な利点は、コンピュータが数式を解釈し、計算処理を実行する上で非常に効率的であることにある。中置記法では、計算の順序を指定するために括弧を用いたり、「乗除算を先に行う」といった演算子の優先順位を考慮したりする必要がある。しかし、逆ポーランド記法ではこれらの要素が一切不要となり、式の構造自体が計算手順を一意に定める。この単純さから、プログラミング言語のコンパイラやインタプリタ、一部の高機能な電卓の内部処理など、機械的な数式評価が求められる場面で広く利用されている。 私たちが普段慣れ親しんでいる「3 + 4 * 2」のような中置記法は、人間にとっては直感的で理解しやすい反面、コンピュータがこれを正しく計算するためには複雑な手順を踏む必要がある。コンピュータは基本的にプログラムやデータを先頭から順に読み取っていくため、この式を単純に左から右へ評価すると「3 + 4」を先に計算してしまい、誤った結果を導き出す。正しい答えを得るためには、乗算は加算よりも優先度が高いという規則を適用し、「4 * 2」の部分を先に計算しなければならないことを認識する必要がある。また、「(3 + 4) * 2」のように括弧が存在する場合は、括弧内を最優先で計算するという別の規則も解釈しなくてはならない。このように、中置記法の計算には、式全体の構造を把握し、演算子の優先順位や括弧の対応関係を解析する、比較的高度な構文解析処理が不可欠となる。 このコンピュータにとっての複雑さを解消するのが逆ポーランド記法である。前述の通り、演算子を計算対象となるオペランドの後に配置する。例えば、「3 + 4 * 2」という式は、逆ポーランド記法では「3 4 2 * +」と表現される。また、「(3 + 4) * 2」は「3 4 + 2 *」となる。この表記法では、括弧も演算子の優先順位という概念も存在しない。計算の順序は、式を左から右へ読み進める際の数値と演算子の出現順によって、曖昧さなく一意に決定される。 逆ポーランド記法の計算処理には、スタックと呼ばれるデータ構造が用いられるのが一般的である。スタックは、後から入れたデータが先に取り出される「後入れ先出し（Last-In, First-Out, LIFO）」という原則で動作する。逆ポーランド記法で書かれた式を計算するアルゴリズムは非常に単純である。まず、式を左から右へ一つずつ読み取っていく。読み取った要素が数値であればスタックに積む（プッシュする）。要素が演算子であれば、スタックから演算に必要な数（例えば加算や乗算なら二つ）を取り出して（ポップして）計算を実行する。そして、その計算結果を再びスタックに積む。この操作を式の最後まで繰り返すと、最終的にスタックには計算結果の数値が一つだけ残る。 具体的な例として、「3 4 2 * +」の計算過程を追ってみる。まず、式を左から走査する。最初に「3」を読み取る。これは数値なのでスタックに積む。スタックの状態は [3] となる。次に「4」を読み取り、同様にスタックに積む。スタックは [3, 4] となる。続いて「2」を読み取り、スタックに積む。スタックは [3, 4, 2] となる。次に演算子「*」を読み取る。スタックから数値を二つ取り出す。最後に入れた「2」、その前の「4」が順に取り出される。そして「4 * 2」を計算し、結果である「8」をスタックに戻す。スタックの状態は [3, 8] となる。最後に演算子「+」を読み取る。スタックから「8」と「3」を取り出し、「3 + 8」を計算する。結果の「11」をスタックに戻す。スタックは [11] となる。これで式の最後まで読み取りが完了したので、スタックに残っている「11」が最終的な計算結果である。 もう一つの例、「3 4 + 2 *」も同様に処理できる。まず「3」と「4」を順にスタックに積む。スタックは [3, 4] となる。次に演算子「+」を読み取る。スタックから「4」と「3」を取り出し、「3 + 4」を計算して結果の「7」をスタックに戻す。スタックは [7] となる。次に「2」を読み取り、スタックに積む。スタックは [7, 2] となる。最後に演算子「*」を読み取る。スタックから「2」と「7」を取り出し、「7 * 2」を計算して結果の「14」をスタックに戻す。スタックは [14] となり、これが最終結果である。このように、逆ポーランド記法は、コンピュータが数式を機械的に、かつ効率的に処理するために考案された優れた表記法であり、構文解析のロジックを大幅に単純化できる。この利点から、コンパイラがソースコード中の中置記法の数式を、実行可能な機械語コードに変換する際の中間表現などとして活用されている。なお、演算子をオペランドの前に置く「ポーランド記法（前置記法）」も存在するが、スタックを用いたアルゴリズムの実装のしやすさから、一般的には逆ポーランド記法の方が広く採用されている。