このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。 なお、今回の演習については補足を参照して 下さい。
今回から計算をコンピュータで行うためのアルゴリズムを取り上げます。 まず、文字列を読んで数字の列を数に変換するプログラムを考えます。 実際、この処理はしばしば使われるため、システムで提供しています。 stdlib.h にある atoi 関数や、stdio.h にある sprintf 関数などです。 しかし、ここではこれらの関数を用いずに、どのようにすれば関数を実現でき るかを考えましょう。
文字が 2 3 4 とならんでいた時、これが二百三十四であるということをどう やったら計算できるのでしょうか? まず、以前大文字小文字の変換で説明したように、 C 言語では文字同士の足 し算引き算ができ、また、文字は順番にならんでいることを仮定できることを 思い出しましょう。 すると、文字 '2' と文字 '0' は 2 だけ離れているので、 '2'-'0' は 2 に なります。同じように数字を表すそれぞれの文字に対して、 '0' を引くこと で、その数字単独で表す数が得られます。
次に数字の列をどのようにしたら一つの数として計算できるかを考えましょう。 各数字は桁を表しています。 2 3 4 だと、 2 が百の位、 3 が十の位、 4 が一の位です。 従って、百が 2 個、十が 3 個、一が 1 個を合わせると二百三十四が得られ ることになります。つまり、 2 × 100 ＋ 3 × 10 ＋ 4 × 1 を計算すれば よいことになります。 ところが、数は常に 3 桁ではありません。文字列を左から見ていく時、どの ように位取りをすれば良いでしょうか?
ここで帰納的に考えてみましょう。 もし、数字の列を左から計算できたとします。そして、次の文字を読み込んだ ことを考えます。 例として、 "2 3 4" に対し、 "2 3" を読み込んで正しく二十三と計算した後、 '4' を読み込んだことを考えます。 この時、どのようにすれば 二百三十四を計算できるでしょうか? 筆算で考えると、二十三を左に移動して、四を足せば良いことが分かります。
このためには既に分かっている値に 10 をかけてから、読んだ文字の示す値を 足せば良いことが分かります。 プログラムにすると次のようになります。
int atoi(char *p){
int res=0;
while(*p!='\0'){
res *= 10;
res += *p - '0';
p++;
}
return res;
}
このようにすると文字列中の数字の列の表す数を計算することができます。
上の関数をテストするプログラムを書き、実際に文字列を数字に変換できるこ とを確かめなさい。
次に、1+1= のような「『数1』『演算子』『数2』=」 という形の式を計算す ることを考えましょう。 プログラムとしては、数1を読み込み、演算子を読み、数2を読み込み、=を読 んだら計算をするという手順を取ります。 このプログラムの手順は、入力の文字の種類に応じて変化します。 数を読み始めたら『数1を読み込み』という手順に入り、数以外(演算子)を読 んだら『演算子を読み』の手順に移り、再び数を読み込んだら『数2を読み込 み』の手順に移ります。 このように入力にしたがってプログラムの状態が変化する様子を整理する図に 状態遷移図があります。
丸が各状態を表し、矢印が状態の移り変わりを示します。 何もないところから入ってくる矢印がついている丸は開始状態で、二重丸は終 了状態です。 矢印の上に入力される文字を記入します。 1 番の状態では数字を読み込み数を計算します。 2 番の状態で演算子を記憶し、 3 番の状態で再び数字を読み込み数を計算し ます。最後の状態で値を計算します。
この状態遷移図をプログラムにするには、基本的には if 文と goto 文を使え ば済みますが、現在のプログラミングスタイルには適合しません。 ここでは enum 宣言と while 文と switch 文を使う手法を説明します。
有限個の値を取る変数を使いたい場合に、その値を列挙した値だけの型を定義 できます。このような型を列挙型と言います。C 言語では enum 宣言で列挙型を作ることができます。 enum 宣言は次のように使います。
enum threestate {first, second, third};
enum threestate state;
state=first;
if(state==second){
...
}
enum も struct 同様に typedef が使用できます。typedef を使うと次のよう に書けます。
typedef enum {first, second, third} threestate;
threestate state;
state=first;
if(state==second){
...
}
switch 文は if()else if()else if() ... という構文を簡略化したものです。 但し、比較には整数値、文字、列挙型の値しか使えません。構文は次のように なります。
switch(変数){
case 値1: 文1-1;
文1-2;
break;
case 値2: case 値3:
文2-1;
break;
default: 文3-1;
文3-2;
}
変数が case で示される値に一致するとそこに書かれている文を 次々と実行します。 case は複数重ねられますので、次の case が来てもそこで文の実行は終らず、 次々と文を実行します。 どの case にも適合しなかった場合、defalutの後の文を実行しま す。 文の実行を止めるには break 文を使います。break 文を使うと switch 文の外に実行が移ります。 break 文は switch 文だけでなく while, for 文などで使うことができます。
switch 文と enum を利用して上記の状態遷移図をプログラムにしたものを示 します。 状態を enum で定義し、 while 文の中に状態の変数に対する switch 文を入 れます。 そして各 case で処理を実行します。
#include <stdio.h>
typedef enum {NUM1, OP, NUM2, END} STATE;
main(){
char c;
STATE s=NUM1;
int num1=0;
int num2=0;
int result=0;
char op;
while((c=getchar())!=EOF){
switch(s){
case NUM1:
if((c>='0')&&(c<='9')){
s=NUM1;
}else{
#ifdef DEBUG
printf("%d\n",num1);
#endif
s=OP;
}
break;
case OP:
s=NUM2;
break;
case NUM2:
if((c>='0')&&(c<='9')){
s=NUM2;
}else if(c=='='){
s=END;
#ifdef DEBUG
printf("%d\n",num2);
#endif
}
break;
}
switch(s){
case NUM1:
num1 *= 10;
num1 += c -'0';
break;
case OP:
op=c;
break;
case NUM2:
num2 *= 10;
num2 += c -'0';
break;
case END:
switch(op){
case '+':
result=num1+num2;
break;
case '-':
result=num1-num2;
break;
case '*':
result=num1*num2;
break;
case '/':
result=num1/num2;
break;
}
break;
}
if(s==END){
printf("%d\n",result);
break;
}
}
}
このプログラムが正常に動くことを次の式を計算させて確かめなさい。
マイナスの値を扱うにはどうすれば良いですか?
連続した計算を行うにはどうすれば良いですか? 但し、ここでは安い電卓のように、完全に左から計算を行い、かけ算が優先さ れるなどのルールはないとします。
状態遷移図のより詳しい内容を知りたい時、「オートマトン」をキーワードと して探して下さい。 また、正規表現はオートマトンと密接な関係があります。 他に、コンパイラの字句解析にも詳しい解説があります。