基本情報技術者 2018年 秋期 午後 問08

解答の導き方

1. 括弧の深さに応じて、優先順位が変わります。
   解析処理では、括弧を開くとnestを一定量だけ増やし、閉じると同じ量だけ減らします。そして、＋や－にはnestに1を加えた値を、×や÷にはnestに2を加えた値を優先順位として設定します。
   例えば、括弧を開くときにnestを増やす量が10の場合、図1では外側の×の優先順位は2、括弧内の－は11、さらに内側の＋は21、括弧内の÷は12です。計算処理では、優先順位が最も高い演算子が先に選ばれるので、内側の演算から計算できます。
2. 優先順位が同じ場合は、先に現れた演算子が選ばれます。
   計算処理では、現在の演算子より優先順位が高い演算子が見つかったときだけ、選ぶ演算子を変更します。そのため、優先順位が同じなら、式の左側にある演算子が選ばれたままです。
3. 内側の演算子は、外側の演算子より必ず高い優先順位にします。
   まず、括弧の外側のnestを $n$、括弧を開いたときに増やす量を $C$ とします。
   書き換え前の設定では、外側で最も高い優先順位は、×や÷の $n+2$ です。一方、括弧の内側で最も低い優先順位は、＋や－の $n+C+1$ です。
   括弧の内側を先に計算するには、内側の最も低い優先順位でも、外側の最も高い優先順位を上回る必要があります。
   $n+C+1>n+2$
   両辺から $n$ を引くと、$C+1>2$、つまり $C>1$ です。$C$ は整数なので、$C$ は2以上でなければなりません。したがって、aは「2以上」です。
   もし $C=1$ だと、例えば2×(3＋4) では、外側の×も内側の＋も優先順位が2になります。同じ優先順位なら左側の×が先に選ばれるため、括弧の内側を先に計算できません。
4. priLowとpriHighに書き換えた場合も、同じ条件で考えます。
   外側で最も高い優先順位は $n+\mathrm{priHigh}$、内側で最も低い優先順位は $n+C+\mathrm{priLow}$ です。内側を必ず先にする条件は、次のとおりです。
   $n+C+\mathrm{priLow}>n+\mathrm{priHigh}$
   整理すると、$C>\mathrm{priHigh}-\mathrm{priLow}$ です。$C$ は整数なので、必要なのは次の条件です。
   $C\ge \mathrm{priHigh}-\mathrm{priLow}+1$
   よって、bは「priHigh − priLow + 1以上」です。差と同じ値では優先順位が同じになり、括弧の内側を先にできないため、さらに1が必要です。

誤りやすいポイント

• 「括弧の内側の優先順位が外側以上」でよいと考えないようにしましょう。同じ優先順位では、左側の演算子が選ばれることがあるため、内側は外側より大きくする必要があります。
• nestを増やす量は10でなくても構いません。大切なのは、内側の演算子の優先順位が外側の演算子を上回ることです。
• priHighとpriLowの差をそのままnestの増加量にすると、内側と外側の優先順位が同じになります。整数で、かつ厳密に上回る条件にするため、差に1を加えます。

FAQ

解答の導き方

• ケース1：（12＋3＋1）×4×2
  左から計算すると、括弧内は（12＋3）＋1＝16で、外側は（16×4）×2＝128です。
  右から計算すると、括弧内は12＋（3＋1）＝16で、外側は16×（4×2）＝128です。
  どちらも128になります。
• ケース2：（12＋3＋1）÷4÷2
  括弧内は、左右どちらから計算しても16です。
  左から計算すると、（16÷4）÷2＝2です。右から計算すると、16÷（4÷2）＝8です。結果が異なります。
• ケース3：（12−3−1）×4×2
  左から計算すると、括弧内は（12−3）−1＝8で、外側は（8×4）×2＝64です。
  右から計算すると、括弧内は12−（3−1）＝10で、外側は10×（4×2）＝80です。結果が異なります。
• ケース4：（12−3−1）÷4÷2
  左から計算すると、括弧内は（12−3）−1＝8で、外側は（8÷4）÷2＝1です。
  右から計算すると、括弧内は12−（3−1）＝10で、外側は10÷（4÷2）＝5です。結果が異なります。

誤りやすいポイント

• 行⑦の条件が優先順位の大小を比べるだけでなく、同じ優先順位の演算子のどちらを選ぶかも決める点を見落としやすいです。
• 「<」では同じ値の場合に選ぶ位置が更新されず、「≤」では更新されます。この違いが、左から計算するか右から計算するかにつながります。
• ＋や×では今回のケースのように計算順を変えても結果が同じことがありますが、−や÷では結果が変わることがあります。ケース1だけの結果から、どの演算でも順序は関係ないと判断しないようにします。

FAQ

解答の導き方

• 数字の「2」を読むと、$Value[0]$ に2が入ります。
• 「×」を読むと、$Operator[0]$ に「×」、$Priority[0]$ に2が入ります。その後、$OpCnt$ が1になり、次の値を入れる場所である $Value[1]$ に0が入ります。
• 「（」を読むと、$nest$ が10になります。
• 「−」を読むと、$Operator[1]$ に「−」が記録されます。符号が「＋」又は「−」の場合、優先度は $nest+1$ なので、$Priority[1]$ は11です。その後、$OpCnt$ は2になり、$Value[2]$ に0が入ります。
• 数字の「1」を読むと、$Value[2]$ が1になります。

誤りやすいポイント

• $f$ を−1と考えないようにします。図3は解析処理の直後の状態です。この時点ではまだ計算していないため、$Value[1]$ は0です。−1になるのは計算処理で「0−1」を実行した後です。
• $OpCnt$ は、計算する演算子の数を表します。符号の「−」も演算子として記録されるので、この式では「×」と「−」の二つを数えます。
• 符号の「−」があるから誤答になる、と判断しないようにします。プログラムは0を使って符号の計算を表せます。
• 優先度を見るときは、括弧の中で増えた $nest$ も考慮します。図3では、括弧内の「−」の優先度11が「×」の優先度2より高くなります。

FAQ