逆ポーランド記法の計算機の作り方を教えてください

[なつみかん]

入力を逆ポーランド記法で行う計算機を作る課題がでました。C言語です。

逆ポーランド記法
１＋２＊３ は計算の優先順位がはっきりするようにカッコを付けて書くと
（１＋（２＊３））である。
演算子（四則演算など）をはさむ二つの項に対して演算するこの記法は、中置記法と呼ばれ、私たちが通常記述する記法はこの記法である。
これに対して、前置き記法・後置き記法と呼ばれる記法がある。たとえば、１＋２を前置き記法で記述すると、＋ １ ２。後置記法で記述すると １ ２ ＋ となる。後置記法は逆ポーランド記法とも呼ばれ、2 項演算子が出現したとき、その直前の 2 項を対象に演算を行うため、カッコがなくても演算の順序はきまる。演算は、演算子がでてくるまではスタックと呼ばれる箱に演算項をいれておき、演算子がでてきたら、スタックから演算項を二つ取り出して、演算を行い、その結果を再びスタックにいれておくことで実現する。

基本仕様
●入力は逆ポーランド記法で行う。
●fgets()で文字列として配列に読み込み、^d の入力でプログラムを終了する。
●数字列（実数を含む）を数値に変換する関数を作成する。
●各項は、空白もしくは演算子によって区切られる。
●スタックは実数型配列を用いて表現する
●四則演算が可能であるとする
●単項演算子は考えなくてよい 例えば －５（マイナス５）など

実行例 （＾D で終了する）
１ ２ ３ ＊ ＋
計算結果 ７．０００
１ ２ ＋ ３ －
計算結果 ０．０００
１ ２ ３ ＊ ＋ ４ ５ ６ ＋ ／ ＋
計算結果 ７．３６４

教科書やインターネットを参考にして自分なりにプログラムを作ったのですがセグメンテーション違反のようです。
本当はfgets()で入力を行わないといけませんし、大域変数も使用してはいけません。
いろんな情報をかき集めてつくったので自分でもよくわからないプログラムになってしまいました。。。
一応プログラムソースを載せておきます。
基本仕様にあったプログラムを教えていただけると幸いです。

コード:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#define N 100
#define num '0'

void ungetch(int);

//文字列の入力
int getStr(char str[])
{
        int i,c;

        while((str[0]=c=getch())==' ' || c=='\t');
        str[1] = '\0';

        if(!isdigit(c) && c != '.'){    //cが数でないならcを返す
                return c;
        }
        i=0;
        if(isdigit(c)){         //cが1～9なら取り込む
                while (isdigit(str[i++]=c=getch()));
        }
        if(c=='.'){             //cが小数点なら取り込む
                while (isdigit(str[++i]=c=getch()));
                str[i]='\0';
        }
        if (c!=EOF){
                ungetch(c);
        }

        return num;
}

double stack[N];

//fを値スタックにプッシュする
double push(double f,int *sp)
{
        if(*sp<N){
                stack[(*sp)++]=f;
        }else{
                printf("error: stack full, can't push %g\n", f);
        }
}

//スタックをポップし，一番上の値を返す
double pop(int sp)
{
        if(sp>0){
                return stack[--sp];
        }else{
                printf("error: stack empty\n");
                return 0.0;
        }
}

char buf[N];
int bufp =0;

int getch(void) /* 1文字を取ってくる */
{
        return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetch(int c) /* 文字を入力に戻す */
{
        if (bufp >=N)
                printf("ungetch: too many characters\n");
        else
                buf[bufp++] = c;
}
main()
{
        int type,sp;
        double op2;
        char str[N];

        while((type = getStr(str)) != EOF) {
                switch (type) {
                        case num:
                                push(atof(str),&sp);
                                break;
                        case '+':
                                push(pop(sp) + pop(sp),&sp);
                                break;
                        case '*':
                                push(pop(sp) * pop(sp),&sp);
                                break;
                        case '-':
                                op2 = pop(sp);
                                push(pop(sp) - op2,&sp);
                                break;
                        case '/':
                                op2 = pop(sp);
                                if (op2 != 0.0){
                                        push(pop(sp) / op2,&sp);
                                }else{
                                        printf("error: zero divisor\n");
                                }
                                break;
                        case '\n':
                                printf("%.3f\n", pop(sp));
                                break;
                        default:
                                printf("error: unknown command %s\n", str);
                                break;
                }
        }
        return 0;
}

[みけCAT]

とりあえず、push関数にはspのポインタを渡しているのに、pop関数にはspの値を渡しており、popをしてもmain関数のspを更新しないのはまずいと思います。

その他、コンパイラの警告を貼ります。

コード:

prog.c: In function 'getStr':
prog.c:15:9: warning: implicit declaration of function 'getch' [-Wimplicit-function-declaration]
        while((str[0]=c=getch())==' ' || c=='\t');
        ^
prog.c: At top level: prog.c:74:1: warning: return type defaults to 'int' [-Wreturn-type]
main()
^
prog.c: In function 'push':
prog.c:46:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^

• getch関数が使用される場所の前にgetch関数の定義またはプロトタイプ宣言を書くべきです
• main関数の返り値の型はint、引数の型はvoidまたはint, char**にするべきです
• push関数の戻り値の型がvoidでないので、returnを用いて戻り値を指定するべきです

他にもまずい場所があり、これだけを修正しても動作は改善しないようです。
ただし、

基本仕様にあったプログラムを教えていただけると幸いです。

という希望を叶えられるかはわかりません。

[なつみかん]

返信ありがとうございます。わかる範囲で修正を行いました。

コード:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#define N 100
#define num '0'

int getch(void);
void ungetch(int);

//文字列の入力
int getStr(char str[])
{
        int i,c;

        while((str[0]=c=getch())==' ' || c=='\t');
        str[1] = '\0';

        if(!isdigit(c) && c != '.'){    //cが数でないならcを返す
                return c;
        }
        i=0;
        if(isdigit(c)){         //cが1～9なら取り込む
                while (isdigit(str[i++]=c=getch()));
        }
        if(c=='.'){             //cが小数点なら取り込む
                while (isdigit(str[++i]=c=getch()));
                str[i]='\0';
        }
        if (c!=EOF){
                ungetch(c);
        }

        return num;
}

double stack[N];

//fを値スタックにプッシュする
void push(double f,int *sp)
{
        if(*sp<N){
                stack[(*sp)++]=f;
        }else{
                printf("error: stack full, can't push %g\n", f);
        }
}

//スタックをポップし，一番上の値を返す
double pop(int sp)
{
        if(sp>0){
                return stack[(sp)--];
        }else{
                printf("error: stack empty\n");
                return 0.0;
        }
}

char buf[N];
int bufp =0;

int getch(void) /* 1文字を取ってくる */
{
        return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetch(int c) /* 文字を入力に戻す */
{
        if (bufp >=N)
                printf("ungetch: too many characters\n");
        else
                buf[bufp++] = c;
}
int main(void)
{
        int type,sp;
        double op2;
        char str[N];

        while((type = getStr(str)) != EOF) {
                switch (type) {
                        case num:
                                push(atof(str),&sp);
                                break;
                        case '+':
                                push(pop(sp) + pop(sp),&sp);
                                break;
                        case '*':
                                push(pop(sp) * pop(sp),&sp);
                                break;
                        case '-':
                                op2 = pop(sp);
                                push(pop(sp) - op2,&sp);
                                break;
                        case '/':
                                op2 = pop(sp);
                                if (op2 != 0.0){
                                        push(pop(sp) / op2,&sp);
                                }else{
                                        printf("error: zero divisor\n");
                                }
                                break;
                        case '\n':
                                printf("%.3f\n", pop(sp));
                                break;
                        default:
                                printf("error: unknown command %s\n", str);
                                break;
                }
        }
        return 0;
}

ポインタのところがよくわからなかったので、具体的に教えてもらえると嬉しいです。。。
他にもお気づきの点がありましたらご指導お願いします。

[milfeulle]

“逆ポーランド記法の計算機の作り方”がわからないのでしょうか? それとも原理は分かっているが、上手くプログラムに変換できないのでしょうか?

例えば11+を入力したら、1をスタックに積み、1をスタックに積み、そして+が来たらスタックから2つ取り出して足した値をスタックに積みますよね。そのようなプログラムが書けているでしょうか? そのためには、

1. 数値と記号を振り分けて入力できる必要がありますができていますか? printfで表示するだけしてみましょう。
また、getStr関数とgetch関数とungetch関数の動作を説明してください。
2. スタックがしっかり出来ていますか?
PUSH 10
PUSH 20
POP ← 20が出てきますか?
POP ← 10が出てきますか?
スタック単体で動くことを確認して下さい。

今回のプログラムでは、spは「スタックポインタ」(もちろん、C言語のポインタとは関係ないです)ですよね。spは初めにいくつでしょうか? このプログラムで、spだけに着目して脳内でプログラムがどう実行されているか1行ずつ追っていって下さい。C言語では初期化しないローカル変数の値は不定です。

そして、関数に変数を渡す時、その渡した数を変更して欲しいならポインタを渡します。渡していない箇所があったりなかったりしますが、どうしてでしょうか?

3. 1.と2.ができたら最後に計算機ができているか確認しましょう。

オフトピック

それと、省略した書き方が多用されていますね……。これで分かるなら一向にかまわないのですが、「buf[--bufp] 」とか「buf[bufp++]」とか即座にどういった動きで、また意図したとおりに動いているか判断できますでしょうか? それと、ifやelseの括弧は省略したりしなかったり統一性がないので慣れないうちは{ }括弧を入れたほうがいいです。