逆ポーランド記法

逆ポーランド記法

逆ポーランド記法を使えば、式の計算をする（評価）には、先頭からひとつずつ順番に記号を読み込み、その記号が演算子以外であればスタックに値を積み、演算子であればスタックから値を取り出して演算し結果をスタックに積む、という簡単な操作の繰り返しだけでよい。そのため、プログラミング初心者の練習課題として、逆ポーランド記法の電卓を作ることがよく行われる。

逆ポーランド記法による計算の例

2+3を計算するとき，逆ポーランド記法では，次のように表す．数値や演算子（+, -, *, /）の間にはスペースを設ける．

これはいくつかのメモリー（記憶場所）が準備されているとき，

• 2を1番目のメモリーに記憶
• 3を2番目のメモリーに記憶
• 1番目のメモリーの内容と2番目のメモリーの内容を加算
• 加算結果を1番目のメモリーに記憶

という手順で計算することを表している．

特徴：

1. 日本語の並びと同じ計算順序
2. 逆ポーランドには括弧がない
3. キータッチ数は最少

【中置記法】
3 * ( 1 + 2 ) / ( ( 4 – 5 ) / ( 6 + 7 ) ) =　　キータッチ数は22回

【逆ポーランド記法】
3 1 2 + * 4 5 – 6 7 + / /　　　　　　　　　　　キータッチ数は13回

問題

次のような機能を持つ電卓プログラムを実現せよ。

1. 基本機能
   1. 演算子は+,-,*,/を許す。
   2. 被演算子にはdouble型を許す。
   3. 式の記法には逆ポーランド記法を用いよ。
   4. 演算子=により結果を表示する。
2. 数学関数
   1. sin,cos,tan,exp,sqrなど

文字列解析、配列によるスタック実装など、総合的な演習問題としてよく使われます。K&Rにも同様の演習があります。

回答例

#define STACK_DEPTH 100
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<math.h>

double stack[STACK_DEPTH];
int sp=STACK_DEPTH;

double pop(void){ return (sp<STACK_DEPTH)?stack[sp++]:0.0; }
void push(double f){ if(sp>0)stack[--sp]=f; }
int getword(char* dst, const char* str, int limit) {
    int i, j, len = strlen(str);
    for(i=0; i<len && isspace(str[i]); i++);
    for(j=0; j<limit && (j+i)<len && !isspace(str[i+j]); j++) dst[j]=str[i+j];
    dst[j]='\0';
    return i+j;
}

int main(void)
{
    char line[100], tmp[100];
    int i, c;
    while(1){
        i = 0;
        fgets(line, 100, stdin);
        while((c=getword(tmp, &line[i], 100)) && strlen(tmp)){
            if(strcmp(tmp, "sin")==0) push(sin(pop())); else
            if(strcmp(tmp, "cos")==0) push(cos(pop())); else
            if(strcmp(tmp, "sqr")==0) push(pow(pop(),2)); else
            if(strcmp(tmp, "+")==0) push(pop()+pop()); else
            if(strcmp(tmp, "-")==0) push(pop()-pop()); else
            if(strcmp(tmp, "*")==0) push(pop()*pop()); else
            if(strcmp(tmp, "/")==0) push(pop()/pop()); else
            if(strcmp(tmp, "=")==0) printf("%f\n", pop()); else
            push(atof(tmp));
            i+=c;
        }
        if (line[0] == '\n') break;
    }
    return 0;
}