【C言語】逆ポーランド記法で計算するプログラムの書き方

2023-09-072024-07-22

この記事では、逆ポーランド記法(RPN)という計算方法について学びます。

逆ポーランド記法は、数式を簡単に評価できる便利な方法です。

この記事を読むことで、逆ポーランド記法の基本概念や利点、具体的な例を理解し、C言語を使って逆ポーランド記法の計算プログラムを作成する方法を学ぶことができます。

目次から探す

逆ポーランド記法とは

逆ポーランド記法(Reverse Polish Notation, RPN)は、数式を表現する方法の一つで、演算子をオペランドの後に置く記法です。

通常の中置記法(Infix Notation)とは異なり、括弧を使わずに計算の順序を明確にすることができます。

逆ポーランド記法の基本概念

逆ポーランド記法では、演算子がオペランドの後に配置されます。

例えば、通常の中置記法で 3 + 4 は逆ポーランド記法では 3 4 + となります。

この記法の特徴は、計算の順序が明確であり、括弧を使わずに計算を行うことができる点です。

逆ポーランド記法の基本的なルールは以下の通りです：

数字(オペランド)はそのままスタックに積む。
演算子が出てきたら、スタックから必要な数のオペランドを取り出し、計算を行う。
計算結果を再びスタックに積む。

逆ポーランド記法の利点

逆ポーランド記法にはいくつかの利点があります：

括弧が不要：計算の順序が明確であるため、括弧を使わずに数式を表現できます。
評価が簡単：スタックを使って簡単に数式を評価できます。

これにより、コンピュータプログラムでの実装が容易になります。

一貫性：演算子の優先順位や結合性を考慮する必要がないため、一貫した方法で数式を評価できます。

逆ポーランド記法の例

具体的な例を見てみましょう。

以下にいくつかの数式を中置記法と逆ポーランド記法で比較して示します。

中置記法	逆ポーランド記法
3 + 4	3 4 +
(5 – 2) * 8	5 2 – 8 *
7 + (6 * 5^2 + 3)	7 6 5 2 ^ * 3 + +

これらの例からわかるように、逆ポーランド記法では演算子がオペランドの後に来るため、計算の順序が明確になります。

例えば、 (5 - 2) * 8 は 5 2 - 8 * と表現され、まず 5 2 - が計算され、その結果に 8 * が適用されます。

次に、逆ポーランド記法を使って実際に計算を行うプログラムの設計と実装について詳しく見ていきましょう。

逆ポーランド記法の評価

逆ポーランド記法(RPN: Reverse Polish Notation)を評価するためには、入力された式を解析し、適切に計算を行う必要があります。

ここでは、逆ポーランド記法の評価方法について詳しく説明します。

トークンの分割

まず、入力された逆ポーランド記法の式をトークンに分割します。

トークンとは、数字や演算子などの最小単位のことです。

例えば、式 3 4 + 2 * は 3 、 4 、 + 、 2 、 * というトークンに分割されます。

C言語では、strtok関数を使って文字列をトークンに分割することができます。

以下に例を示します。

#include <stdio.h>
#include <string.h>
int main() {
    char expression[] = "3 4 + 2 *";
    char *token = strtok(expression, " ");
    
    while (token != NULL) {
        printf("%s\n", token);
        token = strtok(NULL, " ");
    }
    
    return 0;
}

このプログラムは、入力された式をスペースで区切り、各トークンを表示します。

数字の処理

トークンが数字である場合、その数字をスタックにプッシュします。

スタックはLIFO(Last In, First Out)構造であり、逆ポーランド記法の評価に非常に適しています。

以下に、数字をスタックにプッシュする例を示します。

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
int stack[MAX_STACK_SIZE];
int top = -1;
void push(int value) {
    if (top < MAX_STACK_SIZE - 1) {
        stack[++top] = value;
    } else {
        printf("スタックがいっぱいです。\n");
    }
}
int pop() {
    if (top >= 0) {
        return stack[top--];
    } else {
        printf("スタックが空です。\n");
        return -1;
    }
}
int main() {
    push(3);
    push(4);
    printf("スタックのトップ: %d\n", pop());
    printf("スタックのトップ: %d\n", pop());
    
    return 0;
}

このプログラムは、数字をスタックにプッシュし、スタックからポップする例を示しています。

演算子の処理

トークンが演算子である場合、スタックから必要な数のオペランドをポップし、演算を行います。

結果は再びスタックにプッシュします。

以下に各演算子の処理方法を示します。

加算

加算の場合、スタックから2つのオペランドをポップし、その和をスタックにプッシュします。

int a = pop();
int b = pop();
push(b + a);

減算

減算の場合、スタックから2つのオペランドをポップし、その差をスタックにプッシュします。

int a = pop();
int b = pop();
push(b - a);

乗算

乗算の場合、スタックから2つのオペランドをポップし、その積をスタックにプッシュします。

int a = pop();
int b = pop();
push(b * a);

除算

除算の場合、スタックから2つのオペランドをポップし、その商をスタックにプッシュします。

int a = pop();
int b = pop();
if (a != 0) {
    push(b / a);
} else {
    printf("ゼロ除算エラー\n");
}

エラーチェック

逆ポーランド記法の評価中に発生する可能性のあるエラーをチェックすることも重要です。

例えば、スタックが空のときにポップしようとした場合や、ゼロ除算が発生した場合などです。

以下に、エラーチェックを含む完全なプログラムの例を示します。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
int stack[MAX_STACK_SIZE];
int top = -1;
void push(int value) {
    if (top < MAX_STACK_SIZE - 1) {
        stack[++top] = value;
    } else {
        printf("スタックがいっぱいです。\n");
    }
}
int pop() {
    if (top >= 0) {
        return stack[top--];
    } else {
        printf("スタックが空です。\n");
        return -1;
    }
}
int main() {
    char expression[] = "3 4 + 2 *";
    char *token = strtok(expression, " ");
    
    while (token != NULL) {
        if (isdigit(token[0])) {
            push(atoi(token));
        } else {
            int a = pop();
            int b = pop();
            switch (token[0]) {
                case '+':
                    push(b + a);
                    break;
                case '-':
                    push(b - a);
                    break;
                case '*':
                    push(b * a);
                    break;
                case '/':
                    if (a != 0) {
                        push(b / a);
                    } else {
                        printf("ゼロ除算エラー\n");
                        return -1;
                    }
                    break;
                default:
                    printf("不明な演算子: %s\n", token);
                    return -1;
            }
        }
        token = strtok(NULL, " ");
    }
    
    printf("結果: %d\n", pop());
    
    return 0;
}

このプログラムは、逆ポーランド記法の式を評価し、結果を表示します。

エラーチェックも含まれており、ゼロ除算や不明な演算子に対する対処も行っています。