逆ポーランド記法 | やさしい基礎理論

矢沢久雄
2024-07-10 更新

この連載は、基本情報技術者試験の受験者を対象としたものです。

多くの受験者が苦手としている「情報の基礎理論」の分野から毎回1つずつテーマをあげて、やさしくポイント解説と問題解説を行います。苦手分野を克服して、試験の得点をアップしましょう。

今回のテーマは、逆ポーランド記法です。

1 通常の計算式を逆ポーランド記法に変換する
2 スタックを使って逆ポーランド記法の計算式の値を得る
3 逆ポーランド記法に関する問題の例（その1）
4 逆ポーランド記法に関する問題の例（その2）

通常の計算式を逆ポーランド記法に変換する

ふだん私たちが使っている通常の計算式では、「A＋B」のように値と値の間に演算子を置きます。これを「中置記法」と呼びます。
中置記法の計算式の値を求めるには、演算の優先順位を考慮したり、カッコの中を先に演算したりする必要があるので、プログラムで処理しにくいものです。

たとえば、A＋B×(CーD)という計算式をプログラムで処理するとしましょう。

先頭から1文字ずつ取り出していくと、Aの次に＋がありますが、それより先にある×の優先順位が高いので、すぐには＋の演算ができません。
さらに、×より先にカッコで囲まれた部分があるので、そこを先に演算しなければなりません。
これをプログラムで実現するのは、かなり困難でしょう。

今回のテーマである「逆ポーランド記法」は、プログラムで処理しやすいものです。
「AB＋」のように、値と値の後に演算子を置きます。
逆ポーランド記法という名称は、ポーランドの論理学者によって考案されたことに由来します。
演算子が後にあるので「後置記法」とも呼ばれます。

先ほどのA＋B×(CーD)という計算式を逆ポーランド記法にすると、ABCD－×＋になります。
逆ポーランド記法では、演算を優先するカッコが不要になり、後で説明しますが、スタックを使った手順で計算式の値を容易に求められます。

以下の4つの例で、通常の計算式を逆ポーランド記法にする練習をしましょう。

ポイントは、以下の3点です。
・「値」「演算子」「値」という表現を「値」「値」「演算子」にすること
・「値」「値」「演算子」の部分が演算結果の「値」になること
・「値」「値」「演算子」の部分の演算が必ず行われるのでカッコで囲む必要がないこと

【練習】

例1　：　A＋B
例2　：　A＋B×C
例3　：　(A＋B)×(C－D)
例4　：　X＝A＋B－C

例1は、「AとBを足す」なので、AB＋になります。
「値」「演算子」「値」という表現を「値」「値」「演算子」にすることがポイントです。

例2は、「Aに、BとCを掛けた値を、足す」なので、ABC×＋になります。
BC×の部分が演算結果の「値」になることがポイントです。

例3は、「AとBを足した値に、CからDを引いた値を、掛ける」なので、AB＋CDー×になります。
AB＋とCD－の部分が演算結果の「値」になることと、それぞれの演算が必ず行われるのでカッコで囲む必要がないことがポイントです。

例4は、「Xに、AとBを足した値から、Cを引いた値を、代入する」なので、XAB＋C－＝になります。
変数への代入も演算とみなします。

スタックを使って逆ポーランド記法の計算式の値を得る

以下に、逆ポーランド記法の計算式の値を得る手順を説明します。

スタックは、データを積み上げる形式で格納するバッファ（データを一時的に格納する配列）であり、最後に格納したデータが最初に取り出されます。
スタックにデータを格納することを「プッシュする」、スタックからデータを取り出すことを「ポップする」といいます。

【逆ポーランド記法の計算式の値を得る手順】

（1）逆ポーランド記法の計算式の先頭から順に1文字ずつ取り出す。

（2）取り出した文字が値（変数や数値）ならスタックにプッシュする。

（3）取り出した文字が演算子ならスタックから2つのデータをポップし、両者の演算結果の値をスタックにプッシュする。

（4）（1）に戻って繰り返し、最後の文字を取り出して処理したら、その時点でスタックに残っている1つの値が計算式の値である。

どうして、この手順で逆ポーランド記法の計算式の値が得られるかわかりますか。

逆ポーランド記法の計算式は、「値」「値」「演算子」となっているので、値ならすぐに処理せずにスタックにプッシュし、演算子ならその前に2つの値がスタックにプッシュされているので、それらを取り出して演算を行い、演算結果が値となるのでスタックにプッシュします。
これを計算式の最後の文字まで繰り返すと、スタックに1つの値が残り、それが計算式の値になるのです。

逆ポーランド記法に関する問題の例（その1）

逆ポーランド記法に関する問題を2つ紹介しましょう。
はじめは、通常の計算式を逆ポーランド記法にする問題です。

問1（出典：H24春問4）

後置記法(逆ポーランド記法)では、例えば、式 Y＝(A－B)×C を YAB－C×＝と表現する。
次の式を後置記法で表現したものはどれか。

Y＝(A＋B)×(C－D÷E)

ア　YAB＋C－DE÷×＝
イ　YAB＋CDE÷－×＝
ウ　YAB＋EDC÷－×＝
エ　YBA＋CD－E÷×＝

Y＝(A＋B)×(C－D÷E)は、以下のように考えます。

　「Yに」「AとBを足した値と」「CからDをEで割った値を引いた値を」「掛けた値を」「代入する」
　↓
　Y「AとBを足した値と」「CからDをEで割った値を引いた値を」「掛けた値を」＝
　↓
　Y「AB＋」「CからDE÷を引いた値を」「掛けた値を」＝
　↓
　Y「AB＋」「CDE÷－」「×」＝
　↓
　YAB＋CDE÷－×＝

したがって、YAB＋CDE÷－×＝という逆ポーランド記法になり、選択肢イが正解です。

逆ポーランド記法に関する問題の例（その2）

次は、スタックを使って逆ポーランド記法の計算式の値を得る手順の問題です。

この問題では、計算式の値を得るのではなく、計算式の値を得るのに必要とされるスタックの最大の深さ（スタックに格納される最大の要素数）を求めます。
問題に示された例を真似して、スタックの絵を書いてみましょう。

問1（出典：H25春問6）

図は，逆ポーランド表記法で書かれた式 abcd+++ をスタックで処理するときのスタックの変化の一部を表している。
この場合，スタックの深さは最大で 4 となる。最大のスタックの深さが最も少ない逆ポーランド表記法の式はどれか。

ア　ab+c+d+　　　イ　ab+cd++　　　ウ　abc++d+　　　エ　abc+d++

選択肢アのab＋c＋d＋という計算式の値は、以下の手順で得られます。
スタックの最大の深さは、2です。

選択肢イのab＋cd＋＋という計算式の値は、以下の手順で得られます。
スタックの最大の深さは、3です。

選択肢ウのabc＋＋d＋という計算式の値は、以下の手順で得られます。
スタックの最大の深さは、3です。

選択肢エのabc＋d＋＋という計算式の値は、以下の手順で得られます。
スタックの最大の深さは、3です。

スタックの最大の深さが最も少ないのは、選択肢アの2です。
したがって、選択肢アが正解です。

基本情報技術者試験の公開問題を見ると、過去に出題された問題の再利用が多いことがわかります。
したがって、試験に合格するために最も効率的で効果的な学習方法は、過去問題を数多く解き、できなかった問題があれば、できるようになるまで練習することです。
もしも、今回取り上げた問題がすぐにできなかったら、できるようになるまで練習してください。

それでは、またお会いしましょう！