首記のタイトルの本をガイドにして、K&R への何度目かの挑戦で 4 章の逆ポーランド電卓のプログラムまでたどり着きました。このプログラムは K&R の中では有名なプログラムのようです。
一番下のソースコードを下記のようにコンパイルして、実行してみてください。
gcc -Wall -o rpcalc rpcalc.c
下記に実行例を示します。電卓を終了するにはキーボードから Ctrl + d ( Windows では Ctrl + z ) を入力して、EOF をプログラムに送ります。
$ ./rpcalc
100 1 2-4 5+*+ --> 100 + (1 - 2) * (4 + 5)
91
1 2-4 5+*100+ --> (1 - 2) * (4 + 5) + 100
91
.1.2-.4.5+* --> (0.1 - 0.2) * (0.4 + 0.5)
-0.09
.1.2/.4.5+* --> (0.1 / 0.2) * (0.4 + 0.5)
0.45
電卓プログラムには次のような関数が使われています。
| 関数 | 説 明 |
|---|---|
| void push( double f ) | double f を val スタックにプッシュする |
| double pop( void ) | スタックから一番上の値をポップして返す |
| double val[ ] | 値のスタック ( 深さは最大 99 ) |
| int getop( char s[ ] ) | 次の演算子あるいは数値を取って来る |
| char s[ ] | 数値の文字列を格納する配列 |
| int getch( void ) | バッファに文字があればその文字を読み込む。 なければ入力から 1 文字読み込む |
| void ungetch( int c ) | バッファに 1 文字保存する |
| char buf[ ] | unget 用のバッファ |
単語は非英数字を検出したときに、単語が完結します。この非英数字は ungetch でバッファ buf[ ] に保存し、次の文字を読み込むときには、バッファに文字があればまずその文字から読み込むようにしています。
電卓プログラムは、配列をスタックとして扱い、push と pop という操作で計算を進めます。例えば、
1 2 - 4 5 + * --> (1 - 2) * (4 + 5) = -9
を計算するときのスタック ( val[ ] ) の pop と push の動きは以下のようになります。
① 1 と 2 を push
val:[1][2][ ][ ][ ]...[ ]
↑sp
② ' - ' が来て pop( 2 回目 ) - pop( 1 回目 ) = 1 - 2
val:[1][2][ ][ ][ ]...[ ]
↑sp
③ 引き算の結果 -1 を push
val:[-1][2][ ][ ][ ]...[ ]
↑sp
④ 4 と 5 を push
val:[-1][4][5][ ][ ]...[ ]
↑sp
⑤ ' + ' が来て pop ( 1 回目 ) + pop ( 2 回目 ) = 5 + 4
val:[-1][4][5][ ][ ]...[ ]
↑sp
⑥ 足し算の結果 9 を push
val:[-1][9][5][ ][ ]...[ ]
↑sp
⑦ ' * ' が来て pop ( 1 回目 ) * pop ( 2 回目 ) = 9 * ( -1 )
val:[-1][9][5][ ][ ]...[ ]
↑sp
⑧ かけ算の結果 -9 を push
val:[-9][9][5][ ][ ]...[ ]
↑sp
⑨ ' \n ' が来て pop( ) == -9 を印字
val:[-9][9][5][ ][ ]...[ ]
↑sp
また、数値は、式の一部かもれしない、本来数字ではない文字を一つ余計にプログラムで読みこまないと完結しません。そこでこの読み込んだ文字をバッファ ( buf[ ] ) に格納しておき、次の getch( ) では、バッファに格納された文字をまず読むようにしています。
例えば、100+ を順に読み込む場合、
① i = 3 で getop( ) 関数の while ループの isdigit ( s [ 3 ] = c = getch( ) ) が false になる。
s:[1][0][0][+][ ]...[ ]
↑i=3
② [ 1 ][ 0 ][ 0 ] までを数字と判定して最後に ' \0 'を入れます。
s:[1][0][0][\0][ ]...[ ]
③ c == ' + ' を buf[ ] に格納します ( ungetch(c) )。
buf:[+][ ]...[ ]
↑bufp
④ 次の getch( ) は bufp > 0 なので -- bufp として buf に格納した ' + ' をまず読み込みます。
それでは、
12.3 4.5- --> 12.3 - 4.5 = 7.8
を入力として、プログラムに沿って動作を検証してみます。参照しやすいにように行番号を付けたソースコードを掲載しておきます。
1 #include <stdio.h>
2 #include <stdlib.h> /* atof( ) 用 */
3
4 #define MAXOP 100 /* 被演算数、演算子の最大サイズ */
5 #define NUMBER '0' /* 数字があったという記号 */
6
7 int getop(char []);
8 void push(double);
9 double pop(void);
10
11 /* 逆ポーランド電卓プログラム */
12 int main(int argc, char *argv[])
13 {
14 int type;
15 double op2;
16 char s[MAXOP];
17
18 while((type = getop(s)) != EOF) {
19 switch (type) {
20 case NUMBER:
21 push(atof(s));
22 break;
23 case '+':
24 push(pop() + pop());
25 break;
26 case '*':
27 push(pop() * pop());
28 break;
29 case '-':
30 op2 = pop();
31 push(pop() - op2);
32 break;
33 case '/':
34 op2 = pop();
35 if (op2 != 0.0)
36 push(pop() / op2);
37 else
38 printf("error: zero divisor\n");
39 break;
40 case '\n':
41 printf("\t%.8g\n", pop());
42 break;
43 default:
44 printf("error: unknown command %s\n", s);
45 break;
46 }
47 }
48 return 0;
49 }
50
51 #define MAXVAL 100 /* val スタックの最大の深さ */
52
53 int sp = 0;
54 double val[MAXVAL];
55
56 /* push: f を値スタックにプッシュする */
57 void push(double f)
58 {
59 if (sp < MAXVAL)
60 val[sp++] = f;
61 else
62 printf("error: stack full, can't push %g\n", f);
63 }
64
65 /* pop: スタックから一番上の値をポップして返す */
66 double pop(void)
67 {
68 if (sp > 0)
69 return val[--sp];
70 else {
71 printf("error; stack empty\n");
72 return 0.0;
73 }
74 }
75
76 #include <ctype.h>
77
78 int getch(void);
79 void ungetch(int);
80
81 /* getop: 次の演算子あるいは数値の被演算数を取ってくる */
82 int getop(char s[])
83 {
84 int i, c;
85
86 while ((s[0] = c = getch()) == ' ' || c == '\t')
87 ;
88 s[1] = '\0';
89 if (!isdigit(c) && c != '.')
90 return c; /* 数ではない */
91 i = 0;
92 if (isdigit(c)) /* 整数部を集める */
93 while (isdigit(s[++i] = c = getch()))
94 ;
95 if (c == '.') /* 小数部を集める */
96 while (isdigit(s[++i] = c = getch()))
97 ;
98 s[i] = '\0';
99 if (c != EOF)
100 ungetch(c);
101 return NUMBER;
102 }
103
104 #define BUFSIZE 100
105
106 char buf[BUFSIZE]; /* ungetch 用のバッファ */
107 int bufp = 0; /* buf 中の次の空き位置 */
108
109 int getch(void) /* (押し戻された可能性もある) 1 文字を取って来る */
110 {
111 return (bufp > 0) ? buf[--bufp] : getchar();
112 }
113
114 void ungetch(int c) /* 文字を入力に戻す */
115 {
116 if (bufp >= BUFSIZE)
117 printf("ungetch: too many characters\n");
118 else
119 buf[bufp++] = c;
120 }
$\boxed 1$ "12.3 " の読み込み
18 while((type = getop(s)) != EOF)
{
86 | while((s[0] = c = getch()) == ' ' || c == '\t')
111 | | return (bufp > 0) ? buf[--bufp] : getchar()
| | --> return (0 > 0) ? buf[--bufp] : getchar()
| | --> retrun (False) ? buf[--bufp] : getchar()
| | --> return getchar()
| | "12.3 4.5-<Enter>" と入力
| | --> return '1'
86 | while((s[0] = c = '1') == ' ' || c == '\t')
| --> while(False || False) --> while(False)
88 | s[1] = '\0'
89 | if(!isdigit(c)) && c != '.') --> if(!isdigit('1')) && '1' != '.')
| --> if(False && True) --> if(False)
91 | i = 0
92 | if(isdigit(c)) --> if(isdigit('1')) --> if(True)
| {
93 | | while(isdigit(s[++i] = c = getch()))
111 | | | return (bufp > 0) ? buf[--bufp] : getchar()
| | | --> return (0 > 0) ? buf[--bufp] : getchar()
| | | --> retrun (False) ? buf[--bufp] : getchar()
| | | --> return getchar() --> return '2'
93 | | while(isdigit(s[1] = c = '2')) --> while(True)
93 | | while(isdigit(s[++i] = c = getch()))
111 | | | return (bufp > 0) ? buf[--bufp] ] getchar()
| | | --> return (0 > 0) ? buf[--bufp] : getchar()
| | | --> retrun (False) ? buf[--bufp] : getchar()
| | | --> return getchar() --> --> return '.'
93 | | while(isdigit(s[3] = c = '.')) --> while(False)
| }
95 | if(c == '.') --> if(True)
| {
96 | | while(isdigit(s[++i] = c = getch()))
111 | | | return (bufp > 0) ? buf[--bufp] ] getchar()
| | | --> return (0 > 0) ? buf[--bufp] : getchar()
| | | --> retrun (False) ? buf[--bufp] : getchar()
| | | --> return getchar() --> --> return '3'
96 | | while(isdigit(s[4] = c = '3') --> while(True)
96 | | while(isdigit(s[++i] = c = getch()))
111 | | | return (bufp > 0) ? buf[--bufp] ] getchar()
| | | --> return (0 > 0) ? buf[--bufp] : getchar()
| | | --> retrun (False) ? buf[--bufp] : getchar()
| | | --> return getchar() --> --> return ' '
96 | | while(isdigit(s[5] = c = ' ') --> while(False)
| }
98 | s[i] = '\0' --> s[5] = '\0'
99 | if(c != EOF) --> if(True)
| {
100 | | ungetch(c) --> ungetch(' ')
116 | | | if(bufp >= BUFSIZE) --> if(0 >= 100) --> if(False)
118 | | | else
119 | | | buf[bufp++] = c --> buf[0] = ' ', bufp++ --> bufp = 1
| }
101 | return NUMBER
}
18 while((type = NUMBER) != EOF) --> while(True)
{
19 | switch(type) --> switch(NUMBER)
| {
20 | | case NUMBER:
21 | | push(atof(s)) --> push(atof("12.3") --> push(12.3)
| | f = 12.3
68 | | if(sp < MAXVAL) --> if(0 < 100) --> if(True)
69 | | val[sp++] = f --> val[0] = 12.3, sp++ --> sp = 1
22 | | break
| }
}
$\boxed 2$ " 4.5-" の読み込み
18 while((type = getop(s)) != EOF)
86 | while((s[0] = c = getch()) == ' ' || c == '\t')
111 | | return (bufp > 0) ? buf[--bufp] : getchar()
| | --> return (1 > 0) ? buf[--bufp] : getchar()
| | --> retrun (True) ? buf[--bufp] : getchar()
| | --> return buf[--bufp] --> --bufp, return buf[0]
| | --> bufp = 0, return ' '
86 | while((s[0] = c = ' ') == ' ' || c == '\t')
| --> while(True || False) --> while(True)
87 | | ;
86 | while((s[0] = c = getch()) == ' ' || c == '\t')
111 | | return (bufp > 0) ? buf[--bufp] : getchar()
| | --> return (0 > 0) ? buf[--bufp] : getchar()
| | --> retrun (False) ? buf[--bufp] : getchar()
| | --> return getchar() --> return '4'
86 | while((s[0] = c = '4') == ' ' || c == '\t')
| --> while(False || False) --> while(False)
88 | s[1] = '\0'
89 | if(!isdigit(c)) && c != '.') --> if(!isdigit('4')) && '1' != '.')
| --> if(False && True) --> if(False)
91 | i = 0
92 | if(isdigit(c)) --> if(isdigit('4')) --> if(True)
| {
93 | | while(isdigit(s[++i] = c = getch()))
111 | | | return (bufp > 0) ? buf[--bufp] ] getchar()
| | | --> return (0 > 0) ? buf[--bufp] : getchar()
| | | --> retrun (False) ? buf[--bufp] : getchar()
| | | --> return getchar() --> --> return '.'
93 | | while(isdigit(s[1] = c = '.')) --> while(False)
| }
95 | if(c == '.') --> if(True)
| {
96 | | while(isdigit(s[++i] = c = getch()))
111 | | | return (bufp > 0) ? buf[--bufp] ] getchar()
| | | --> return (0 > 0) ? buf[--bufp] : getchar()
| | | --> retrun (False) ? buf[--bufp] : getchar()
| | | --> return getchar() --> --> return '5'
96 | | while(isdigit(s[3] = c = '4') --> while(True)
96 | | while(isdigit(s[++i] = c = getch()))
111 | | | return (bufp > 0) ? buf[--bufp] ] getchar()
| | | --> return (0 > 0) ? buf[--bufp] : getchar()
| | | --> retrun (False) ? buf[--bufp] : getchar()
| | | --> return getchar() --> --> return '-'
96 | | while(isdigit(s[4] = c = '-') --> while(False)
| }
98 | s[i] = '\0' --> s[4] = '\0'
99 | if(c != EOF) --> if(True)
| {
100 | | ungetch(c) --> ungetch('-')
116 | | | if(bufp >= BUFSIZE) --> if(0 >= 100) --> if(False)
118 | | | else
119 | | | buf[bufp++] = c --> buf[0] = '-', bufp++ --> bufp = 1
| }
101 | return NUMBER
18 while((type = NUMBER) != EOF) --> while(True)
19 | switch(type) --> switch(NUMBER)
| {
20 | | case NUMBER:
21 | | push(atof(s)) --> push(atof("4.5") --> push(4.5)
| | f = 4.5
68 | | if(sp < MAXVAL) --> if(1 < 100) --> if(True)
69 | | val[sp++] = f --> val[1] = 4.5, sp++ --> sp = 2
22 | | break
| }
$\boxed 3$ "-\n" の読み込みと演算
18 while((type = getop(s)) != EOF)
86 | while((s[0] = c = getch()) == ' ' || c == '\t')
111 | | return (bufp > 0) ? buf[--bufp] : getchar()
| | --> return (1 > 0) ? buf[--bufp] : getchar()
| | --> retrun (True) ? buf[--bufp] : getchar()
| | --> return buf[--bufp] --> --bufp, return buf[0]
| | --> bufp = 0, return '-'
86 | while((s[0] = c = '-') == ' ' || c == '\t')
| --> while(True || False) --> while(False)
86 | while((s[0] = c = getch()) == ' ' || c == '\t')
111 | | return (bufp > 0) ? buf[--bufp] : getchar()
| | --> return (0 > 0) ? buf[--bufp] : getchar()
| | --> retrun (False) ? buf[--bufp] : getchar()
| | --> return getchar() --> return '\n'
86 | while((s[0] = c = '\n') == ' ' || c == '\t')
| --> while(False || False) --> while(False)
88 | s[1] = '\0'
89 | if(!isdigit(c)) && c != '-') --> if(!isdigit('-')) && '-' != '.')
| --> if(True && True) --> if(True)
90 | return c --> return '-'
18 while((type = '-') != EOF) --> while(True)
19 | switch(type) --> switch('-')
| {
29 | | case '-':
30 | | op2 = pop()
68 | | | if(sp > 0) --> if(2 > 0) --> if(True)
69 | | | return val[--sp] --> --sp = 1, return val[1]
| | | --> return 4.5
68 | | op2 = 4.5
31 | | push(pop() - op2)
68 | | | if(sp > 0) --> if(1 > 0) --> if(True)
69 | | | return val[--sp] --> --sp = 0, return val[0]
| | | --> return 12.3
31 | | push(12.3 - 4.5) --> push(7.8)
| | f = 7.8
59 | | if(sp < MAXVAL) --> if(0 < 100) --> if(True)
60 | | val[sp++] = f --> val[0] = 7.8, sp++ = 1
22 | | break
| }
18 while((type = getop(s)) != EOF)
86 | while((s[0] = c = getch()) == ' ' || c == '\t')
111 | | return (bufp > 0) ? buf[--bufp] : getchar()
| | --> return (0 > 0) ? buf[--bufp] : getchar()
| | --> retrun (False) ? buf[--bufp] : getchar()
| | --> return getchar() --> return '\n'
86 | while((s[0] = c = '\n') == ' ' || c == '\t')
| --> while(False || False) --> while(False)
88 | s[1] = '\0'
89 | if(!isdigit(c)) && c != '-') --> if(!isdigit('-')) && '-' != '.')
| --> if(True && True) --> if(True)
90 | return c --> return '\n'
18 while((type = '\n') != EOF) --> while(True)
19 | switch(type) --> switch('\n')
| {
40 | | case '\n':
41 | | printf("\t%.8g\n", pop())
68 | | | if(sp > 0) --> if(1 > 0) --> if(True)
69 | | | return val[--sp] --> --sp = 0, return val[0]
| | | --> return 7.8
41 | | printf("\t%.8g\n", 7.8)
| | 7.8
42 | | break
| }
$\boxed 4$ EOF の読み込み
18 while((type = getop(s)) != EOF)
86 | while((s[0] = c = getch()) == ' ' || c == '\t')
111 | | return (bufp > 0) ? buf[--bufp] : getchar()
| | --> return (0 > 0) ? buf[--bufp] : getchar()
| | --> retrun (False) ? buf[--bufp] : getchar()
| | --> return getchar()
| | "Ctrl-d (EOF)<Enter>" を入力
| | --> return 'EOF'
86 | while((s[0] = c = '\n') == ' ' || c == '\t')
| --> while(False || False) --> while(False)
88 | s[1] = '\0'
89 | if(!isdigit(c)) && c != 'EOF') --> if(!isdigit('EOF')) && 'EOF' != '.')
| --> if(True && True) --> if(True)
90 | return c --> return 'EOF'
18 while((type = 'EOF') != EOF) --> while(False)
48 return 0
K&R では関数ごとにばらばらに書かれていたプログラムを一つにまとめましたので、コンパイルして実行してみてください。スタックを頭に描きながら、いろいろと計算してみると、うまくできていることに少し感動するかもしれません。
#include <stdio.h>
#include <stdlib.h> /* atof( ) 用 */
#define MAXOP 100 /* 被演算数、演算子の最大サイズ */
#define NUMBER '0' /* 数字があったという記号 */
int getop(char []);
void push(double);
double pop(void);
/* 逆ポーランド電卓プログラム */
int main(int argc, char *argv[])
{
int type;
double op2;
char s[MAXOP];
while((type = getop(s)) != EOF) {
switch (type) {
case NUMBER:
push(atof(s));
break;
case '+':
push(pop() + pop());
break;
case '*':
push(pop() * pop());
break;
case '-':
op2 = pop();
push(pop() - op2);
break;
case '/':
op2 = pop();
if (op2 != 0.0)
push(pop() / op2);
else
printf("error: zero divisor\n");
break;
case '\n':
printf("\t%.8g\n", pop());
break;
default:
printf("error: unknown command %s\n", s);
break;
}
}
return 0;
}
#define MAXVAL 100 /* val スタックの最大の深さ */
int sp = 0;
double val[MAXVAL];
/* push: f を値スタックにプッシュする */
void push(double f)
{
if (sp < MAXVAL)
val[sp++] = f;
else
printf("error: stack full, can't push %g\n", f);
}
/* pop: スタックから一番上の値をポップして返す */
double pop(void)
{
if (sp > 0)
return val[--sp];
else {
printf("error; stack empty\n");
return 0.0;
}
}
#include <ctype.h>
int getch(void);
void ungetch(int);
/* getop: 次の演算子あるいは数値の被演算数を取ってくる */
int getop(char s[])
{
int i, c;
while ((s[0] = c = getch()) == ' ' || c == '\t')
;
s[1] = '\0';
if (!isdigit(c) && c != '.')
return c; /* 数ではない */
i = 0;
if (isdigit(c)) /* 整数部を集める */
while (isdigit(s[++i] = c = getch()))
;
if (c == '.') /* 小数部を集める */
while (isdigit(s[++i] = c = getch()))
;
s[i] = '\0';
if (c != EOF)
ungetch(c);
return NUMBER;
}
#define BUFSIZE 100
char buf[BUFSIZE]; /* ungetch 用のバッファ */
int bufp = 0; /* buf 中の次の空き位置 */
int getch(void) /* (押し戻された可能性もある) 1 文字を取って来る */
{
return (bufp > 0) ? buf[--bufp] : getchar();
}
void ungetch(int c) /* 文字を入力に戻す */
{
if (bufp >= BUFSIZE)
printf("ungetch: too many characters\n");
else
buf[bufp++] = c;
}
最後に K&R を独習するときに参考になる本やサイトを紹介します。
-
カーニハン & リッチー「プログラミング言語Ｃ」を読む 小林健一郎著 講談社
すでに絶版のようで中古か図書館でしか見ることができませんが、ガイドブックとして最適です。 -
Ｃアンサーブック クロビス･L･トンド 著・ スコット･E･ギンペル 著・ 矢吹 道郎 訳 共立出版
K&R の豊富な演習問題の解答集です。解答の簡潔な説明がありがたいです。 -
Serendip Web Studio
Ｃアンサーブックでは、解答として関数しか書いていないことがありますが、こちらのサイトでは main プログラムを追加して実行例まで紹介されています。テストプログラムの作り方も参考になります。