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

解答の論理構成

1. 演算要素に分解
   対象式は “( 2 + 3 ) × 4”。【問題文】の「まず変換前の数式を、数値、演算子及び括弧の要素…に分解する」という説明に従い、
   ① “(” ② “2” ③ “+” ④ “3” ⑤ “)” ⑥ “×” ⑦ “4”
   の 7 要素となります。
2. 優先度の確認
   【問題文】表2「演算要素の優先度」によれば
   “(” は 5、数値は 4、“+” は ア＝「＋」、イ＝「−」で優先度 3、“×” は ウ＝「×」、エ＝「÷」で優先度 2、“)” は 1 です。
3. スタック操作 (手順(1)〜(4))
   ・“(” をスタックにプッシュ。
   ・“2” は数値なので直接変換後配列へ → 2
   ・“+” はスタック先頭が “(” で優先度が低いためプッシュ。
   ・“3” は数値なので変換後配列へ → 2 3
   ・“)” が来たら手順(3)で “)” を破棄し、“(” もポップして破棄。スタックには何も残りません。
   ・“×” をプッシュ。
   ・“4” は数値なので変換後配列へ → 2 3 4
   ・入力終了後、手順(4)でスタックの “×” をポップし変換後配列末尾へ追加。
4. 完成した逆ポーランド表記
   変換後配列は左から “2 3 + 4 ×”。空白を詰めて「23+4×」と書くのが慣例です。

誤りやすいポイント

• “(” と “)” は結果に出力しない
  優先度処理だけに使い、最終式には残りません。
• “×” と “+” の優先度を逆に覚える
  【問題文】表2で“+”は 3、“×”は 2。「数が小さい方が低い」ので注意。
• スタックを空にするタイミング
  入力が終わっても必ず手順(4)でポップし切ることが必要です。

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

解答の論理構成

• 【問題文】には次の記述があります。
  「プログラム中で…ダミーの演算要素 null を定義し、プログラム開始直後にスタックにプッシュしている。
  null がスタックからポップされることがないようにするために、その優先度を オ と定義する。こうすることで、プログラム中、手順②の処理を行う部分で カ の判定処理を記述する必要がなくなり…」
• 手順②は【逆ポーランド表記法への変換アルゴリズム】で
  「(2) スタック上に演算要素がある場合は…」
  と説明されており、通常はスタックが空かどうかを判定してからトップ要素を参照します。
• しかし null をあらかじめプッシュしておけば、スタックが空になるケースは存在しません。
  その結果、手順②で「スタックが空かどうか」を毎回判定するコードが不要になります。
• よって カ は
  「スタック上に演算要素があるか否か」
  （同義語「スタックが空であるか否か」でも可）
  が正答となります。

誤りやすいポイント

• ダミー要素 null の目的を「演算子優先度の比較を簡単にするため」とだけ覚え、スタック空判定の省略につながっている事実を見落とす。
• 手順②を「演算子ＡとＢの優先度比較」と短絡的に理解し、そもそも“スタックが空のときトップ要素は存在しない”という前提を忘れる。
• 「優先度が最も高いからポップされない」という部分だけに注目し、空判定を省けるロジック全体を説明できない。

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