応用情報技術者 2013年 春期 午後 問02

解答の導き方

1. 参照1：'('（優先度5）
   • スタックは空なのでポップはなし。')'でないのでスタックにプッシュ。
   • スタック： (
   • 変換後配列：（空）
2. 参照2：'2'（優先度4）
   • スタック先頭は '('（優先度5）だが「スタックの先頭が '(' の場合はそこで繰り返しを終了する」とあるためポップは行わない。
   • '2'は')'でないのでスタックにプッシュ。
   • スタック： ( , 2（先頭）
   • 変換後配列：（空）
3. 参照3：'＋'（優先度2）
   • スタック先頭は '2'（優先度4）で、4 ≥ 2かつ先頭は '(' でないので '2' をポップして変換後配列へ追加。
   • 次のスタック先頭は '(' なのでポップを止める。
   • '＋'は')'でないのでスタックにプッシュ。
   • スタック： ( , ＋（先頭）
   • 変換後配列： 2
4. 参照4：'3'（優先度4）
   • スタック先頭は '＋'（優先度2）、2 ≥ 4は偽なのでポップしない。
   • '3'をスタックにプッシュ。
   • スタック： ( , ＋ , 3（先頭）
   • 変換後配列： 2
5. 参照5：')'（優先度1）
   • スタック先頭は '3'（優先度4）で4 ≥ 1かつ先頭は '(' でないので '3' をポップして変換後配列へ追加。
   • 次にスタック先頭は '＋'（優先度2）で2 ≥ 1なので '＋' をポップして変換後配列へ追加。
   • 次のスタック先頭は '(' のためポップを停止。
   • 参照要素が ')' なのでこの ')' を破棄し、スタックの先頭にあるはずの '(' もポップして破棄する（手順(3)）。
   • スタック：（空）
   • 変換後配列： 2, 3, ＋
6. 参照6：'×'（優先度3）
   • スタックは空なのでポップはなし。
   • '×'をスタックにプッシュ。
   • スタック： ×（先頭）
   • 変換後配列： 2, 3, ＋
7. 参照7：'4'（優先度4）
   • スタック先頭は '×'（優先度3）、3 ≥ 4は偽なのでポップしない。
   • '4'をスタックにプッシュ。
   • スタック： × , 4（先頭）
   • 変換後配列： 2, 3, ＋
8. 手順(4)：スタックに残った全ての要素を順にポップして変換後配列へ追加（先頭から順にポップするので先に '4'、次に '×' を追加）。
   • 最終の変換後配列： 2, 3, ＋, 4, ×

誤りやすいポイント

• 「'(' は優先度5だが、スタック先頭が '(' のときはそこで繰り返しを終了する」という手順を見落とし、'(' を誤ってポップしてしまう。括弧はグループ区切りなので特別扱いする点を必ず確認すること。
• 表2の ア〜エ の割り当てを誤ると優先度比較が逆になり、乗除と加減の順序を取り違えて誤答になる。正しくは ア=×、イ=÷、ウ=＋、エ=−。
• アルゴリズムでは「参照→（必要な分だけ）スタックからポップ→参照要素をスタックにプッシュ（')' の場合は別処理）」という順序が重要です。処理順を逆にすると出力順が狂います。
• 最後のスタックの取り出し順（先頭からポップして結果に追加）を逆に実装すると演算子の順序が逆になり誤りになります。

FAQ

解答の論理構成

1. 演算子集合の確認
   【問題文】には「演算子には二項演算子 +、−、×、÷ を用い」とあります。したがって空欄 ア〜エ にはこの4つを重複なく配置します。
2. 優先度テーブルの読み取り
   【問題文】の「表2　演算要素の優先度」より、空欄は次の2段階に分かれています。
   ・優先度3 … ア, イ
   ・優先度2 … ウ, エ
   同じ表には「注記　値が大きいほど優先度が高い。」と記載されています。
3. 一般的な四則演算の規則との対応づけ
   一般に「×」「÷」は「+」「−」より高い優先度を持ちます。これは【問題文】冒頭の例「一般的な表記法の数式1+2×3を、逆ポーランド表記法では1 2 3 × + と表記する」からも読み取れます。
   ・先に「×」を評価するためにスタックに残り、後から「+」が出力されている＝「×」のほうが高優先度。
4. 優先度3と優先度2への割当
   よって、優先度3には「×」「÷」、優先度2には「+」「−」を入れれば演算規則と矛盾しません。
   「アとイは順不同、ウとエは順不同」とあるため、具体的な配置は
   ア：×　イ：÷　ウ：+　エ：−
   で成立します。

誤りやすいポイント

• 「値が大きいほど優先度が高い」という注記を読み飛ばし、数字が小さい方が高いと思い込む。
• 「+」「−」と「×」「÷」の4つすべてに異なる優先度があると誤解し、5段階に分けようとする。
• 例「1+2×3」の動作を確認せず、直感だけで割当て順を決定してしまう。
• 「÷」の優先度を「−」と同じにしてしまい、変換テストをするとスタック制御が破綻する。

FAQ

解答の論理構成

• 問題文には「nullがスタックからポップされることがないようにするために、その優先度をオと定義する。」とあります。
• スタックから要素をポップする条件は、アルゴリズム手順(2)の説明と同じくプログラム中でも「スタックの先頭にある演算要素の優先度 ≥ 現在処理中の演算要素の優先度」のときです。
• 表2によれば既存の優先度の最小値は “)” の「1」。したがってnullを決してポップさせないためには、nullの優先度を「1」よりも小さく設定すればよいことになります。
• 非負整数でかつ最小値にしたいので「0」が最適です。
• 以上より、オ には「0」が入ります。

誤りやすいポイント

• nullの役割を「ダミー要素」ではなく「番兵」として理解しないと、優先度を大きくしてしまう誤答が生じやすいです。
• 「1未満にすれば安全」と覚えながらも負の値を想定する受験者がいますが、GetPriorityは「非負の整数」を返す仕様なので負値は選択肢に入りません。
• 表2の優先度を暗記していても、「値が大きいほど優先度が高い」という注記を読み落とし、大小関係を逆に判断するミスも頻発します。

FAQ

解答の導き方

1. 問題文の該当箇所を確認します。プログラムの説明に「nullがスタックからポップされることがないようにするために、その優先度をオと定義する。こうすることで、プログラム中、手順(2)の処理を行う部分でカの判定処理を記述する必要がなくなり、プログラムが簡潔になる。」とあります。これは「手順②で通常必要となるある判定」をプログラムで省略できる、という意味です。
2. 手順(2)の本文を見ます。そこには「スタック上に演算要素がある場合は、スタックの先頭にある演算要素の優先度を参照し、(1)の演算要素の優先度以上なら、スタックの先頭の演算要素をポップし、変換後配列の末尾に追加する。」とあります。ここの先頭の語句「スタック上に演算要素がある場合は」が、そのままプログラムで判定すべき内容を示しています。つまり手順(2)で必要なのは「スタックに要素があるかどうか（＝スタックが空か否か）」を調べることです。
3. 図2のプログラムの初期化を見ると、次のようになっています。「stackCount ← 1」「stack[stackCount] ← null」。この初期化によりスタックには常に少なくともダミー要素nullが入っており、明示的に「スタックが空かどうか」をチェックしなくてもスタックの先頭要素に安全にアクセスできます。したがって、手順(2)で本来必要な判定は「スタック上に演算要素があるか否か（＝スタックが空であるか否か）」であり、これをダミー要素で代替していることが分かります。
4. ただしダミーのnullがポップされてしまうと意味がなくなるため、nullの優先度は全ての通常の演算要素よりも小さく設定します。図2中のポップループは「while ( ク かつstackTopが "(" 以外の間繰り返す )」の形で優先度比較を行っているため、nullの優先度が最も低ければ優先度比較が偽になり、nullは残ったままループを抜けます。

誤りやすいポイント

• nullの優先度を「最も高く」設定してしまう誤り
  • ポップ条件が「stackTopの優先度がelementの優先度以上ならポップ」であるため、nullの優先度が高いと条件を満たしてnullがポップされ、スタック保護の目的を果たせません。nullは「全ての通常の演算要素より低い優先度」にする必要があります。
• 手順(2)の判定を「トップが '('かどうか」と混同する誤り
  • 「トップが '(' の場合はそこで繰り返しを終了する」はポップループ内の追加条件であり、手順(2)冒頭の「スタック上に演算要素がある場合は」とは別のチェックです。前者は括弧処理、後者は空スタックの有無のチェックです。
• 同義語の使い方で減点される心配
  • 「スタック上に演算要素があるか否か」と「スタックが空であるか否か」は同義です。どちらを使っても正答とされます（設問の字数制限に収めることだけ注意）。

FAQ

解答の論理構成

1. 【問題文】の手順(2)は
   “スタックの先頭にある演算要素の優先度を参照し、(1)の演算要素の優先度以上なら、スタックの先頭の演算要素をポップし…”
   と指示しています。コードではスタック先頭を変数stackTopに取り込みます。先頭要素は配列stack[] の末尾、すなわち添字stackCountに格納されているので、stack[stackCount] が最適です。
   ➡︎ キ＝stack[stackCount]
2. 手順(2)の繰返し条件は
   “スタックの先頭の演算要素の優先度が、(1)の演算要素の優先度未満になるまで繰り返す”
   です。すなわち「まだ優先度が高い（または同じ）ならポップを続行」という意味なので、コードのwhile条件は
   GetPriority(stackTop) がelementPriority以上
   となります。
   ➡︎ ク＝GetPriority(stackTop)がelementPriority以上
3. 手順(3)の冒頭には
   “参照した演算要素が“ ) ”なら、それを破棄し…”
   とあります。コード側のif判定はこの条件に対応するため、
   GetElement(i) が “)” である
   が入ります。
   ➡︎ ケ＝GetElement(i)が“)”である

誤りやすいポイント

• スタックの先頭をstack[1] と勘違いする
  • 本プログラムは「右端が先頭」方式です。stackCountが現在のトップであることを忘れやすいので注意。
• while条件を「＞」と書いてしまう
  • 手順(2)は“以上ならポップ”なので「＝」も含めて比較する必要があります。
• “ ) ” 判定をstackTopに対して行うミス
  • 手順(3)はあくまで“(1)で参照した演算要素”の判定です。スタックトップではありません。

FAQ

解答の論理構成

1. 【問題文】では、入力エラーの判定基準として「数値の演算要素が2個以上連続する場合」や「“ ) ” の直後に “ ( ” が続く場合」を例示しています。これは「同じ種類の演算要素が連続する」「演算子同士が連続する」など、数学的に項が不足するパターンを全て排除する方針だと分かります。
2. 表4の行「4 （数値）」×列「4 （数値）」は “数値 → 数値” の並びです。先述の連続数値禁止より【コ】はErrとなります。
3. 同じ行の列「2 （ウ, エ）」は “数値 → 加減算演算子” の並びです。演算子が後ろに来るのは正しい式の形なので【サ】はOKになります。
4. 行「3 （ア, イ）」×列「4 （数値）」は “乗除演算子 → 数値” の並びです。演算子の直後に数値が来るのは正常なので【シ】はOKです。
5. 同じ行の列「2 （ウ, エ）」は “乗除演算子 → 加減算演算子” という “演算子 → 演算子” の並びに該当します。被演算子が欠けているため【ス】はErrになります。

誤りやすいポイント

• 「数値の後ろには必ず演算子か “ ) ” が来る」と覚えていないと、4 → 4を誤ってOKとしてしまう。
• 「演算子の後ろには必ず数値か “ ( ” が来る」ルールを忘れると、演算子 → 演算子 のケースを見落としやすい。
• 優先度の大小に気を取られ、そもそもの“式としての並び”を確認し忘れると判断を誤る。

FAQ