トップC-Tips > 逆ポーランド記法(1)

逆ポーランド記法(1)

1.逆ポーランド記法とは

a + b のような我々が日常に使う数式の記法を中置記法(infix notation)と呼ぶ。 + a b のように、演算子を先頭におく記法を前置記法(prefix notation)と呼ぶ。

これに対して、a b + のように、演算子を後ろにおく記法を後置記法(postfix notation)と呼ぶ。 前置記法の発明者がポーランド人であったことから、 後置記法を、通常、 逆ポーランド記法(reverse polish notation, inverse polish notation)と呼ぶ。

この記法は括弧()が要らず、また、計算は左から右に順に処理を行うことで実行できることから、 コンピュータ処理に適している。

2.逆ポーランド記法インタプリタ

逆ポーランド記法の四則演算の例を下に示す。
No.逆ポーランド記法中置記法
13.2 1.5 4.0 * +3.2 + 1.5 * 4.0
23.2 1.5 * 4.0 +3.2 * 1.5 + 4.0
33.2 1.6 / 4.0 +3.2 / 1.6 + 4.0

逆ポーランド記法の四則演算式を実行するインタプリタ・プログラムを下に示す。 数式のみを対象とする場合、トークン配列は文字列配列でもよいが、 コンパイラへの発展などを考えて、トークンは構造体としている。 数式のエラーは考慮していない。

スタックを用意する。 トークン(この場合、数値か演算子)を左から順に処理する。 数値の場合、スタックにプッシュする。 演算子の場合、スタックから数値を二つポップする。 演算子に従った計算を行い、スタックにプッシュする。

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>

#define REAL  '0'

typedef struct _Token {
    int  type;
    double rval;
} Token;

#define STACK_MAX  100
Token *stack[STACK_MAX];
int   stack_pointer = 0;

void error(char *msg) {
    fprintf(stderr, "error: %s\n", msg);
    exit(1);
}

void push(Token *pToken) {
    if (stack_pointer >= STACK_MAX) error("stack full");
    stack[stack_pointer++] = pToken;
}

Token *pop() {
    return stack_pointer > 0 ? stack[--stack_pointer] : NULL;
}

double execute(char *token[]) {
    int n;
    Token *pToken, *pToken1, *pToken2;

    for (n = 0; token[n] != NULL; n++) {
        pToken = calloc(1, sizeof(Token));
        if (pToken == NULL) error("メモリが確保できません");
        pToken->type = isdigit(token[n][0]) ? REAL : token[n][0];
        if (pToken->type == REAL) {     // 数値
            pToken->rval = atof(token[n]);
            push(pToken);
        } else {                        // 演算子
            pToken2 = pop();
            pToken1 = pop();
            switch (pToken->type) {
              case '+': pToken1->rval += pToken2->rval; break;
              case '-': pToken1->rval -= pToken2->rval; break;
              case '*': pToken1->rval *= pToken2->rval; break;
              case '/': pToken1->rval /= pToken2->rval; break;
              default: error("unknown operator");
            }
            push(pToken1);
            free(pToken2);
            free(pToken);
        }
    }
    pToken = pop();
    double rval = pToken->rval;
    free(pToken);
    return rval;
}

int main() {
    char *expr1[] = { "3.2", "1.5", "4.0", "*", "+", NULL };  // 3.2 + 1.5 * 4.0 = 9.2
    char *expr2[] = { "3.2", "1.6", "/", "4.0", "+", NULL };  // 3.2 / 1.6 + 4.0 = 6.0
    printf("expr1=%.3f, expr2=%.3f\n", execute(expr1), execute(expr2));
}