今週の午後問題〔問題〕アルゴリズム 整数式の解析と計算 2018 年度 秋期

例 1: 2 × (34 – (5 + 67) ÷ 8)

〔プログラム 1 の説明〕

1. 整数式は，文字の列で与えられる。整数式は，次のもので構成される。
   • 符号のない数字 0 ～ 9 の並び
   • 演算子 : +，-，×，÷
   • 括弧: (，)
2. 引数 Expression[] で整数式を，引数 ExpLen で整数式の文字数を，それぞれ受け取る。
3. プログラム中の破線で囲んだ解析処理の部分では，受け取った整数式を解析し，計算に必要な情報を配列及び変数に設定する。
4. プログラム中の破線で囲んだ計算処理の部分では， 3. で設定した情報を用いて，整数式の値を計算する。整数式の値は， Value[0] に得られる。
5. 各配列の添字は， 0 から始まる。各配列の要素数は，十分に大きいものとする。
6. 受け取った整数式に誤りはないものとする。また，計算の過程で，あふれやゼロ除算は発生しないものとする。

infoスマートフォンをご覧の際、プログラムは右にスクロールできます

○整数型関数 : Compute(文字型: Expression[], 整数型: ExpLen)
○文字型: Operator[100]
○整数型: OpCnt, Priority[100], Value[100]
○文字型: chr
○整数型: i, ip, nest
解析処理(詳細は〔プログラム(解析処理の部分)〕に示す)
計算処理(詳細は〔プログラム(計算処理の部分)〕に示す)
･ return Value[0]

〔プログラム (解析処理の部分) の説明〕

1. Expression[] で渡された整数式を解析し，計算に必要な情報を配列 Operator[]，Priority[]，Value[] 及び変数 OpCnt に設定する。関数 int() は，引数の数字が表す値を整数型で返す。
2. 例 1 の整数式について，プログラム(解析処理の部分)を実行した直後の各配列及び変数の状態を，図 1 に示す。
   

   

･ OpCnt ← 0
･ Value[0] ← 0 
･ nest ← 0 
■ i: 0, i < ExpLen, 1
| ･ chr + Expression[i]
| ▲ ('0' ≦ chr) and (chr ≦ '9')        /* 数字 0 ～ 9 か？ */
| | ･ Value[OpCnt] ← 10 x Value[OpCnt] + int(chr)
| ▼
| ▲ (chr = '+') or (chr = '-') or (chr = 'x') or (chr = '÷')
| | ･ Operator [OpCnt] ← chr
| | ▲ (chr = '+') or (chr = '-')
| | | ･ Priority[OpCnt] ← nest + 1
| |-+-----
| | | ･ Priority[OpCnt] ← nest + 2
| | ▼
| | ･ OpCnt ← OpCnt + 1
| | ･ Value[OpCnt] ← 0
| ▼
| ▲ chr = '('
| | ･ nest ← nest + 10
| ▼
| ▲ chr = ')'
| | ･ nest ← nest – 10
| ▼
■

〔プログラム (計算処理の部分) の説明〕

1. 整数式の値を計算していく。図 1 に示す各配列及び変数の状態から，プログラム (計算処理の部分) の最外側の繰返しを 1 回実行した直後の各配列及び変数の状態を，図 2 に示す。
   

   

■ OpCnt > 0
| ･ ip ← 0
| ■ i: 1, i < OpCnt, 1
| | ▲ Priority[ip] < Priority[i]
| | | ･ ip ← i
| | ▼
| ■
| ･ chr ← Operator[ip]
| ▲ chr = '+'
| | ･ Value[ip] ← Value[ip] + Value[ip + 1]
| ▼
| ▲ chr = '-'
| | ･ Value[ip] ← Value[ip] - Value[ip + 1]
| ▼
| ▲ chr = 'x'
| | ･ Value[ip] ← Value[ip] x Value[ip + 1]
| ▼
| ▲ chr = '÷'
| | ･ Value[ip] ← Value[ip] ÷ Value[ip + 1]
| ▼
| ■ i: ip + 1, i < OpCnt, 1
| | ･ Value[i] ← Value[i + 1]
| | ･ Operator[i - 1] ← Operator[i]
| | ･ Priority[i - 1] ← Priority[i]
| ■
| ･ OpCnt ← OpCnt - 1
■

設問 1

プログラム (解析処理の部分) に関する次の記述中のに入れる正しい答えを，解答群の中から選べ。

1arrow_forward ･ Priority[OpCnt] ← nest + priLow
2arrow_forward ･ Priority[OpCnt] ← nest + priHigh

a に関する解答群

ア　1 以上　　イ　2 以上
ウ　11 以下　　エ　12 以下

b に関する解答群

ア　priHigh 以上　　
イ　priHigh + 1 以上
ウ　priHigh – priLow 以上　　
エ　priHigh – priLow + 1 以上

設問 2

優先順位の等しい演算子が複数個含まれている整数式の，演算の実行順序について考察する。プログラムに関する次の記述中のに入れる正しい答えを，解答群の中から選べ。ここで， c1 ～ c3 に入れる答えは， c に関する解答群の中から組合せとして正しいものを選ぶものとする。

c に関する解答群

infoスマートフォンをご覧の際、表は右にスクロールできます

d に関する解答群

ア　1　　イ　1 及び 2
ウ　1 及び 3　　エ　1 及び 4

設問 3

プログラムの動作に関する次の記述中のに入れる正しい答えを，解答群の中から選べ。

　符号付き整定数 (数字の並びの先頭に符号 + 又は – を付けた定数) を含む整数式を考える。符号付き整定数は，例 2 のように括弧で囲んで記述する。ただし，符号付き整定数の直前の文字が演算子でない場合は，例 3 のように括弧で囲まなくてもよい。

例 2: (+2) × ((-3) + (-4))
例 3: +2 × (-3 + (-4))

　符号付き整定数を含む整数式 2 × (-1)についてプログラム (解析処理の部分) を実行した結果を，図 3 に示す。

　このように，符号付き整定数を含む整数式を受け取ったとき，プログラムはe。

e に関する解答群

ア

整数式が符号付き整定数で始まる場合に、正しい値を返さない

イ

整数式中に符号 – の付いた符号付き整定数がある場合に,正しい値を返さない

ウ

整数式中に二つ以上の符号付き整定数が含まれる場合に,正しい値を返さない

工

正しい値を返す

f, g に関する解答群

ア　-1　　イ　0　　ウ　1　　エ　2