科目Bの逆ポーランド記法問題の解き方｜スタックの中身を表で追う

数字が先に並んで、演算子があとから来る。この式、どこから計算すればいいの？

科目Bで逆ポーランド記法の式を見て、手が止まったことはありませんか？

3 4 + のように、ふだん見慣れた式とは並び方がまったく違います。さらにスタックへの出し入れが重なると、いま何が積まれているのかを途中で見失ってしまう人も多いのではないでしょうか。

大丈夫です。逆ポーランド記法の問題は、記号を1つ読むたびにスタックの中身を1行書き足していけば、確実に答えにたどり着けるように作られています。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。逆ポーランド記法そのものを業務で書くことはありませんが、計算式や検索条件を文字列で受け取って処理する機能は何度も作ってきました。

あるとき、利用者が入力した計算式の結果が、引き算のときだけ符号が逆になる不具合に出会いました。原因は、取り出した2つの値の順番を取り違えていたことで、スタックの中身を1行ずつ書き出してようやく気づけました。

この記事では、逆ポーランド記法の問題を、科目Bの解き方に合わせて5つの段階で紹介します。科目B全体の中で、こうしたアルゴリズムの問題がどんな位置にあるのかを先に確かめたい人は、親記事から読んでおくと流れがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

逆ポーランド記法の問題は何を聞いているのか¶

最初に、逆ポーランド記法とは何かを短く押さえておきましょう。逆ポーランド記法とは、演算子を2つの値のうしろに書く式の書き方のことで、後置記法とも呼ばれます。

ふだん使っている 3 ＋ 4 のような書き方は、演算子が値の間にあるので中置記法と呼ばれます。これを逆ポーランド記法で書くと 3 4 ＋ になります。

この書き方のよいところは、かっこがいらないことです。左から順に読み、演算子が来たらその直前の2つの値で計算する、という1つの規則だけで、どんな式でも計算できます。

その直前の2つの値を覚えておく入れ物として使われるのが、スタックです。あとから入れたものを先に取り出す、という性質がちょうど合っているのです。

スタックの出し入れの順番そのものに不安がある場合は、先にこちらの記事で確かめておくと安心です。

【関連記事】科目Bのスタック・キュー問題の解き方｜出し入れの順番を表で追う

中置記法と逆ポーランド記法を並べて比べる¶

まずは、同じ計算を2つの書き方で並べてみます。かっこの位置によって、演算子の並ぶ場所が変わる点に注目してください。

2行目と3行目を見比べると、かっこが無くなった代わりに、演算子の位置で計算の順番が表されているのが分かります。先に計算するものほど、左のほうに演算子が来ます。

4行目は、あとの章で何度も出てくる大事な例です。8 5 − は 8 から 5 を引くという意味で、5 から 8 を引くのではありません。

設問のパターンを表で整理する¶

逆ポーランド記法の設問は、聞かれ方がいくつかの型に分かれます。どの型なのかを最初に見極めると、追うべきものがはっきりします。

この記事では、出題されやすい計算の結果と空欄の穴埋めを中心に追います。途中の状態を問う型は、同じトレース表の途中の行を読むだけで答えられます。

まず目を付ける場所¶

逆ポーランド記法の考え方がつかめたら、次はコードのどこから読むかを決めます。この問題で目を付ける場所は3つです。

ひとつ目は記号が数か演算子かを見分ける条件、ふたつ目は演算子が来たときに pop する順番、みっつ目は最後に何を返しているかです。この3か所が決まれば、あとは記号ごとにスタックを書き足すだけです。

数と演算子を見分ける条件分岐¶

最初に確かめたいのが、読んだ記号が演算子かどうかを判定している if 文です。数なら push し、演算子なら計算する、という2本の枝に分かれているのが基本の形です。

条件分岐の枝をどう追うかに慣れていない場合は、こちらの記事が役に立ちます。

【関連記事】科目Bの条件分岐問題の解き方｜どの枝を通るかを表で追う

pop した値をどちらの変数に入れているか¶

この問題でいちばん大事なのが、演算子が来たときの2回の pop です。最初に取り出した値は、あとから積まれた値、つまり式の右側の値になります。

たとえば 8 5 − なら、最初に取り出されるのは 5 で、次に取り出されるのが 8 です。コードが b ← pop、a ← pop の順になっていれば、計算は a − b で、8 − 5 になります。

足し算と掛け算は順番を入れ替えても結果が同じなので、ここで間違えても気づけません。引き算と割り算の行だけは、どちらの変数が左に来ているかを必ず指で押さえて確かめてください。

最後に返しているものを確かめる¶

最後に見るのが、ループを抜けたあとの return です。式が正しければ、すべての記号を読み終えたとき、スタックには値がちょうど1つだけ残っています。

その1つを pop して返しているのか、別の変数を返しているのかを確かめておきましょう。最後に残る値がそのまま答えになる、という形を覚えておくと迷いません。

例題：逆ポーランド記法の式を計算する関数¶

ここからは、実際の例題で追い方を確かめます。この記事の例題は説明のために作成したもので、IPA の公開問題そのものではありません。

次のプログラムは、逆ポーランド記法の式を1記号ずつ要素に分けた文字列型の配列 tokens を受け取り、計算の結果を返す関数です。配列の要素番号は1から始まります。関数 toInt は、数を表す文字列を整数に変換して返すものとします。

○整数型: calcRPN(文字列型の配列: tokens)
  整数型: i, a, b
  スタック: st
  for (i を 1 から tokens の要素数 まで 1 ずつ増やす)
    if (tokens[i] が "+" または "-" または "*" と等しい)
      b ← pop(st)
      a ← pop(st)
      if (tokens[i] が "+" と等しい)
        push(st, a ＋ b)
      elseif (tokens[i] が "-" と等しい)
        push(st, a − b)
      else
        push(st, a × b)
      endif
    else
      push(st, toInt(tokens[i]))
    endif
  endfor
  return pop(st)

calcRPN は、記号が演算子なら上から2つを取り出して計算し、その結果をまたスタックに積みます。数なら、整数に変えてそのまま積みます。

では、tokens が {"6", "2", "3", "+", "*", "4", "-"} のとき、calcRPN の戻り値はいくつになるでしょうか？

トレース表でスタックの中身を追う¶

頭の中だけで7つの記号を処理すると、スタックに何が残っているのかがすぐに分からなくなります。そこで、記号を1つ読むごとに、行った操作、取り出した b と a、そのあとのスタックの中身をトレース表に書きます。

スタックの中身は、左を底、右を一番上として書くと決めておきます。こうすると、右端から順に取り出されるので、pop の順番を目で追いやすくなります。

すべての記号を読み終えると、スタックには 26 だけが残っています。これを pop して返すので、戻り値は 26 です。

7行目を見てください。最初に取り出した 4 が b に、次に取り出した 30 が a に入っています。計算は a − b なので 30 − 4 になり、−26 にはなりません。

この式を中置記法に戻すと、6 × (2 ＋ 3) − 4 という形になります。かっこの中を先に計算するという順番が、トレース表の4行目と5行目にそのまま表れています。

トレース表の書き方そのものに慣れていない場合は、こちらの記事で基本から確認できます。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

途中の状態を問われたら行で止める¶

設問によっては、5番目の記号を読んだ直後のスタックを聞かれることがあります。そのときは、トレース表の i が5の行で止めて、右端の列を読むだけです。

この例なら、答えはスタックに 30 が1つだけ積まれている状態です。最後まで計算してから戻る必要はありません。

中置記法から変換する問題の考え方¶

中置記法の式を逆ポーランド記法に直す問題も、計算の順番から考えると解けます。先に計算する部分から順に、値を2つ書いて、そのうしろに演算子を書いていくのです。

たとえば 6 × (2 ＋ 3) − 4 なら、まずかっこの中が 2 3 ＋ になります。6 にそれを掛けるので 6 2 3 ＋ ×、最後に4を引いて 6 2 3 ＋ × 4 − となり、例題の tokens とぴったり同じ並びになります。

式を木の形に描いて、左、右、自分の順にたどる帰りがけ順で読むと、そのまま逆ポーランド記法になります。木のたどり方を練習したい人は、こちらの記事も読んでみてください。

【関連記事】科目Bの二分木問題の解き方｜節点をたどる順番を解説

間違いやすい選択肢の見分け方¶

逆ポーランド記法の問題では、pop の順番や計算の向きを少しだけずらした選択肢が並びます。どんな誤りが用意されやすいのかを知っておけば、選択肢を見た瞬間に候補を絞れます。

例題の式を使って、よくある誤りを表にまとめました。

1行目の誤りは、b と a のどちらが左に来るかを確かめなかったときに起きます。答えの符号だけが違う選択肢が並んでいたら、まず引き算の行を見直してください。

3行目の −20 は、底にある 6 と 2 から取り出してしまったときの答えです。あとから積んだ値を先に取り出す、というスタックの性質を外れると、かっこの意味がまるごと崩れてしまいます。

引き算と割り算は具体的な数で試す¶

空欄に a − b と b − a のどちらが入るかを問われたら、8 5 − のような小さな式を代入してみるのが近道です。答えが3になるほうが正解で、−3になるほうは向きが逆です。

割り算でも同じで、8 2 ÷ が4になるか、0.25 のような値になるかで見分けられます。足し算や掛け算の式では違いが出ないので、試すときは必ず引き算か割り算を使ってください。

スタックに残る値の数で検算する¶

式が正しく処理されたかどうかは、スタックに残る値の数でも確かめられます。数を読むと1つ増え、演算子を読むと2つ減って1つ増えるので、差し引き1つ減ります。

例題では数が4つ、演算子が3つなので、最後に残るのは 4 − 3 で1つです。トレース表の途中で値が2つ以上残っていたり、空になったりしていたら、どこかで操作を書き落としています。

再帰で式を計算する形の問題も、内部では同じように一時的な値を積み上げて処理しています。再帰の追い方に不安がある場合は、こちらの記事が参考になります。

【関連記事】基本情報科目Bの再帰呼び出しがわからない人への対策方法を解説｜擬似言語で処理を追うコツ

Giji Academy のシミュレーターで動かす¶

紙のトレース表で動きをつかんだら、最後は実際に動かして確かめましょう。スタックの中身が増えたり減ったりする処理ほど、動かして見る効果は大きくなります。

Giji Academy の擬似言語シミュレーターでは、擬似言語のコードを1行ずつ実行し、変数の値が変わる様子を目で確かめられます。自分で書いたトレース表と見比べながら進めると、どの記号で予想とずれたのかがすぐに分かります。

試すときは、まず例題の7つの記号を順に処理して、7番目の − で b に 4、a に 30 が入る瞬間を確かめてください。そのあと a − b を b − a に書き換えて、答えの符号が逆になる様子を見ると、pop の順番の意味が体で分かります。

慣れてきたら、tokens の並びを自分で変えてみましょう。中置記法の式を1つ決めて、それを逆ポーランド記法に直してから動かし、思ったとおりの答えが出るかを試すのもおすすめです。

まずはGiji Academy の擬似言語シミュレーターで講座を選び、値が積まれ、演算子が来るたびに2つ取り出されて1つに変わっていく流れを確かめてみてください。

まとめ¶

科目Bの逆ポーランド記法の問題は、特別な知識を問うものではありません。左から順に読み、数なら積み、演算子なら上から2つを取り出して計算する、という手順を表に書いて追えば、落ち着いて解けます。

この記事でお伝えした5つの段階を振り返っておきましょう。

最初は、記号が5つから7つくらいの短い式で十分です。何度か表を書くうちに、式を見ただけで、どの演算子でスタックがどう縮むのかが分かるようになります。

最初に取り出した値は式の右側。スタックは左を底にして書く。 この2つを習慣にしておけば、逆ポーランド記法の問題にも自信を持って向き合えます。次に後置記法の式を見かけたら、まずは引き算の行でどちらが左に来るかから確かめてみてください。