平成23年度秋期 情報処理安全確保支援士 午前Ⅰ 問1

スタック（皿の積み上げ）を使って、後置記法の計算を左から順番に進める

逆ポーランド記法（後置記法）の計算アルゴリズムについての問題だよ。後置記法の式（例えば A B +）を計算する時は、左から順に読んでいくんだ。数字が出たら「スタック（皿を積み上げるようなデータ構造）」に置き、演算子（+ や *）が出たら、スタックから必要な数（通常は2つ）の数字を取り出して計算し、その結果を再びスタックに積むんだよ。

この問題で問われていること

コンピュータがスタックを使って「数字が出たら積み、演算子が出たら取り出して計算し、結果を戻す」という一連の処理ステップを正しく理解し、具体的な式の計算結果を求めよう。

Reverse Polish Notation

reverse Polish notation places operators after operands and is evaluated using a stack

push operands\npop on operator\npush result

確認ポイント

• 演算子が先頭には来ない。
• スタックで順に評価する。
• 後置記法を選ぶ。

正解

ウ

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア

これは不正解だよ。1000001は5ビット目を1から0に変えた形だけど、計算で出た間違いの場所は3ビット目。泥棒が3号室にいると分かったのに5号室を直しているようなものなので、直す場所が違うよ。

選択肢イ

これは不正解だよ。1000101は受信したままの符号語だけど、c0やc1が0ではないので「どこかに誤りあり」のサインが出ている。警報が鳴っているのに何も直さないのと同じで、そのままにするのは間違いだよ。

選択肢ウ（正解）

これは不正解だよ。1001101は4ビット目を0から1に変えた形だけど、チェック結果から出る番号は i=3。つまり直すべきなのは左から3ビット目で、4ビット目ではないよ。

選択肢エ

これは正解だよ。受信語1000101を式に入れると、c0=1、c1=1、c2=0になる。だから i=1+1×2+0×4=3。つまり「3番窓口で間違い発見！」という合図なので、左から3ビット目を0から1にひっくり返す。1000101 → 1010101になるよ。