9 算術式の計算

算術式の計算
/ / のような算術式が与えられたときに、その値を
計算するプログラムを考える。プログラムへの入力は、行の算術式で、出力はその算術式の値と
する。
構文の定義
まず、プログラムへ入力される算術式の行の構文 % を図 %% に示す構文図で定義する。
図において、円はその中に書かれた文字を表し、四角は文字列の集合 .四角の中には集合名を記載/
を表し、四角の部分の構文は別の構文図で定義されている。枝の分岐は、分岐先のどれかを選ぶこ
とを意味する。
\n
0
1
2
3
4
5
6
7
8
9
(
)
.
図 ) 構文図
この定義を見ると、直接的には再帰的な定義は行われていないが、式の定義に項が用いられ、
項の定義に因子が用いられ、因子の定義に再び式が用いられているので、間接的に再帰的な定義が
行われている。
この構文図全体で、次のような構文が定義されている。
算術式として正しい文字列の集合を定義している。
行とは、式の後ろに改行文字 .I9"I/ をつけたものである。
式とは、項であるか、あるいは項の後に、二項演算子 I:I またはII を前につけた項を複
数個つなげたものである。
たとえば、「項」、「項 / 項」、「項項」、「項 / 項項」などは式である。
項とは、因子であるか、あるいは因子の後ろに、二項演算子I-I または II を前につけた
因子を複数個つなげたものである。
たとえば、「因子」、「因子 - 因子」、「因子因子」、「因子因子 - 因子」などは項で
ある。
因子とは、定数であるか、あるいは式の前後を括弧でくくったものであるか、あるいは、そ
れらの前に単項演算子 II やI:I をつけたものである。
たとえば、「定数」、「. 式 /」、「定数」、「: . 式 /」などは因子である。
定数とは、数字の列であるか、あるいは、数字の列の後ろに II と数字の列をつけたもの
である。
たとえば、「$%」、「$'&%$」などは定数である。
数字とは、II から II のいずれかの文字である。
この定義によると、たとえば、定数「」は同時に因子でもあり項でもあり式でもある。ま
た、「
/ 」は、因子でもあり、項でもあり、式でもある。
また、この構文定義は、暗に演算子の評価順序 .優先順位 / も与えている。
二項演算子「/ 」は左優先で評価する。たとえば、
「 / 」は「 / 」
のように左側の演算子から順に評価する。
二項演算子「
」は左優先で評価する。たとえば、
「」は「」の
ように左側の演算子から順に評価する。
単項演算子「/ 」の優先順位が最も高く、二項演算子「
」はその次の優先順位を持
つ。二項演算子「/ 」は最も優先順位が低い。たとえば、
「 / 」は「 /
」のように優先度の高い演算子を先に評価する。
括弧「」で括られた部分式は括弧の外側の演算子よりも先に評価する。
プログラムの概要
まずプログラムの全体の構造を決める。 "./ 関数では、行を解釈し、結果を出力するもの
とする。構文図に基づき、式の値を計算する関数を * !
./、項の値を計算する関数を
* !
./、因子の値を計算する関数を * !
"./、定数の値を計算する関数を * !
C や
/ のようにつの数値に対して演算を施す演算子を、二項演算子と呼ぶ。
や C における「」や、C や C
における「C」のようにつの数値に対して演算を施す演算子を、
単項演算子と呼ぶ。「C」と「」は単項演算子として用いられたり二項演算子として用いられたりする。一般の数式では
」や「 C」のように単項演算子を連続して用いることを許す場合もあるが、図の構文図では、単項演算子を連続
「
して用いることは許していない。したがって、例えば「
」のような式は構文誤りとなる（「」は許される）。
優先順位の高い演算子を先に評価計算する。
./、数字の値を計算する関数を " ./ とする。また、文字の入力を担当する関数
を 0* "
= ./ とし、構文誤りを見つけたときにエラーメッセージを出力する関数を 0*
. -/ とする。
これらすべての関数からアクセスできるグローバル変数として、これから処理をする文字を入れ
る文字型変数、先頭から何文字目の処理を行っているかを記憶するための整数型変数
" "、処理を行った文字列を記憶しておくための文字型配列 !"
?@ を用いる。
関数 ./# ./# "./# ./# ./ を呼び出す際には、変数にこれか
ら処理をする文字を入れておくものとする。
先頭部分
G@H .00
)P
G@H!"
行の長さの最大値これから処理をする文字何文字目の処理を行っているか処理を行った文字の列以下は使用する関数のプロトタイプ宣言 %&#' %&#' &#' P
&#'
P&#'
# &#' & '
関数ここでは、" を初期化し、式の値を求め、行末かどうかのチェックを行
い、答えを出力する。
)&#'
*
答え + をに初期化プロンプト出力 &3数式 + 3'
&'
最初の文字入力 + %&'
式の値を求める &)P ++ 252'*
&3答え + 43
' 行末なら答えを出力して正常終了 &'
,
&3行末でない3'
行末でなければエラー出力して終了 ,
関数ここでは、文字入力し、その文字をと !"
?"@ に格納し、
" を増やす。ただし、もし入力された文字のコードが D なら、これは入力終了を意
味するので、エラーメッセージを出力して終了する。また、入力された文字が空白の場合も
エラーメッセージを出力して終了する。
# &#'
*
&& + L&'' ++ @SA'
&3@SA 検出3'
& + G@H'
&3行が長すぎる3'
!!" + )P + に文字入力し、それが @SA ならエラー出力して終了行の長さが最大値を超えればその旨出力してエラー終了入力された文字を )P " に格納後、
図の構文図では、空白文字は許されていない。ここで空白文字を検出してエラーとしなくても他の部分でエラーと
判定されるが、空白文字を誤って入力してしまうことはよくあることだと考えられるため、ここでそれを検出しエラーと
している。
,
& ++ 2 2'
&3空白検出3'
を増やす。入力された文字が空白文字ならエラー出力して終了関数 & ここでは、引数として渡された文字列、"、!"
? @ を出力し、
プログラムを終了する。
# & '
*
&34 文字目で構文誤り 4
53 '
" + 252
配列の内容を文字列として扱うために最後に 252 をつける &34
53 '
ここで出力される最後の文字に誤りがある &'
エラー終了 ,
関数 ' が II ∼ II なら、対応する数値を求め、次の処理に備えて次の文
字を読み込み、求めた数値を返す。そうでなければエラー。
P&#'
*
&&)P + 22' 66 &)P + 2O2''* )P が 22 ∼ 2O2 &数字' なら + )P - 22
その数字に対応する数値を求める &'
次の文字の読み込み ,
&3数字でない3'
ここは実行されないので不要ではあるが、コンパイラの警告を回避するために入れている ,
関数 ' ここでは、構文図に基づき定数の構文チェックを行いながら、定数が表す
値を計算して返す。
P
&#'
*
定数が表す値を入れる ))
小数点以下の値の計算に使用 + P&'
最初の数字の値を求める J&&)P + 22' 66 &)P + 2O2''
数字が続く間を再計算 + ! P&' これまでのを倍して、新しい数値を足す &)P ++ 22'*
小数点かM )) + 最初は小数点以下の桁目なので )) は &'
次の文字を読み込む !+ P&'))
に読み込んだ数字の )) 倍を足す J&&)P + 22' 66 &)P + 2O2''* 数字が続く間を再計算 )) + )) を倍する !+ P&'))
に読み込んだ数字の )) 倍を足す ,
,
,
関数 ( ここでの処理の概略は、次のようになる。
関数 ./ で項の値を求めに代入。
$ がI:I か II
である間次の処理を繰り返す。
./ の値を記憶しておく。
. / 次の文字を読み込む。
./ 次の項の値を求め、に足すか引く。
% を返す。
関数 (
関数 ./ とほぼ同様に実現できる。
関数ここでの処理の概略は、次のようになる。
が II または I:I ならば、そのことを記憶し、次の文字を読み込む。
$ が I.I でないならば、関数 ./ で定数の値を求める。
が I.I ならば、以下の処理を行う。
./ 次の文字を読み込む。
. / 関数 ./ により式の値を求める。
./ が I/I でなければ、「閉じ括弧がない」旨のエラーを出力して終了。
.*/ 次の文字を読み込む。
% 最初の文字の状況 .II またはI:I またはそれ以外/ に応じて、上記で求めた値を適宜
補正し、その結果を返す。
演習 $M 上で説明した算術式の値を計算するプログラムを作成せよ。
ヒント $4. を呼び出すと変数には、次の文字が代入されることに注意。
ヒントこの構文では、数値のみの式も許されるので、次のような順序で動作確認やデバッグを行
えば良い。
まず数値例えばやなどのみの式を入力して同じ値が出力されることを確認
負号付きの数値（例えば ! や ! などで動作確認
個の数値の加算、減算、乗算、除算などで動作確認
括弧の無い式で動作確認
括弧のある式で動作確認
"" や" " は、各々文字「」や文字「」を表す文字「」や文字「」の文字コード。
で記憶した値に基づいて判断する。

Download Report