K&R 「プログラミング言語 C」を読む～逆ポーランド電卓

首記のタイトルの本をガイドにして、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 )|バッファに文字があればその文字を読み込む。<br>なければ入力から 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
```
を入力として、プログラムに沿って動作を検証してみます。参照しやすいにように行番号を付けたソースコードを掲載しておきます。
```c
     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 "** の読み込み
```c
 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-"** の読み込み
```c
 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"** の読み込みと演算
```c
 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** の読み込み
```c
 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 では関数ごとにばらばらに書かれていたプログラムを一つにまとめましたので、コンパイルして実行してみてください。スタックを頭に描きながら、いろいろと計算してみると、うまくできていることに少し感動するかもしれません。
```c
#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 を独習するときに参考になる本やサイトを紹介します。
1. [カーニハン & リッチー「プログラミング言語Ｃ」を読む　小林健一郎著　講談社](https://www.kspub.co.jp/book/detail/1557536.html)
すでに絶版のようで中古か図書館でしか見ることができませんが、ガイドブックとして最適です。
2. [Ｃアンサーブック　クロビス･L･トンド 著・ スコット･E･ギンペル 著・ 矢吹 道郎 訳　共立出版](https://www.kyoritsu-pub.co.jp/book/b10011642.html)
K&R の豊富な演習問題の解答集です。解答の簡潔な説明がありがたいです。
3. [Serendip Web Studio](https://www.serendip.ws/archives/tag/language-c/page/9)
Ｃアンサーブックでは、解答として関数しか書いていないことがありますが、こちらのサイトでは main プログラムを追加して実行例まで紹介されています。テストプログラムの作り方も参考になります。