学習

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

2025-04-15更新日: 2025-04-15

逆ポーランド記法（RPN）は、演算子をオペランドの後に記述する表記法で、計算の優先順位を明示するために括弧を必要としません。

C言語で逆ポーランド記法を用いた計算プログラムを作成するには、スタックを利用してオペランドと演算子を処理します。

スタックは、LIFO（Last In, First Out）構造を持ち、オペランドをプッシュし、演算子が現れた際にポップして計算を行います。

この方法により、効率的に数式を評価することが可能です。

目次から探す

逆ポーランド記法のアルゴリズム
C言語でのプログラム設計
- 必要なデータ構造
- 関数の設計
完成したプログラム
- 実行例
応用例
まとめ

逆ポーランド記法のアルゴリズム

逆ポーランド記法(RPN: Reverse Polish Notation)は、数式を後置記法で表現する方法です。

この記法では、演算子がオペランドの後に記述されるため、括弧を使わずに計算の優先順位を明確にすることができます。

以下では、逆ポーランド記法のアルゴリズムについて詳しく説明します。

スタックを用いた計算方法

逆ポーランド記法の計算にはスタックを用いるのが一般的です。

スタックは、LIFO(Last In, First Out)構造を持つデータ構造で、最後に入れた要素が最初に取り出されます。

この特性を利用して、逆ポーランド記法の数式を効率的に計算します。

オペランドをスタックにプッシュ(追加)する。
演算子が現れたら、スタックから必要な数のオペランドをポップ(取り出し)、計算を行う。
計算結果を再びスタックにプッシュする。

演算子とオペランドの処理

逆ポーランド記法では、数式を左から右に順に処理します。

以下に、演算子とオペランドの処理方法を示します。

オペランド(数値)が現れた場合：
スタックにプッシュします。
演算子(+, -, *, / など)が現れた場合：
スタックから必要な数のオペランドをポップします。
演算を行い、その結果をスタックにプッシュします。

計算の流れと例

具体的な計算の流れを例を用いて説明します。

例えば、次の逆ポーランド記法の数式を考えます。

3 4 + 2 * 7 /

この数式を計算する流れは以下の通りです。

3をスタックにプッシュします。
4をスタックにプッシュします。
+が現れたので、スタックから4と3をポップし、加算して7をスタックにプッシュします。
2をスタックにプッシュします。
*が現れたので、スタックから2と7をポップし、乗算して14をスタックにプッシュします。
7をスタックにプッシュします。
/が現れたので、スタックから7と14をポップし、除算して2をスタックにプッシュします。

最終的にスタックに残る2が計算結果です。

このように、逆ポーランド記法ではスタックを用いることで、括弧なしで計算の優先順位を管理できます。

C言語でのプログラム設計

逆ポーランド記法をC言語で実装するためには、適切なデータ構造と関数を設計することが重要です。

ここでは、スタックを用いたプログラムの設計について説明します。

必要なデータ構造

逆ポーランド記法の計算にはスタックが不可欠です。

スタックを実装するために、ノードとスタック自体のデータ構造を定義します。

スタックの実装

スタックは、ノードの連結リストとして実装します。

以下に、スタックの基本的な操作を行うための構造体と関数を示します。

#include <stdio.h>
#include <stdlib.h>
// ノードの構造体
typedef struct Node {
    double data; // データ部分
    struct Node* next; // 次のノードへのポインタ
} Node;
// スタックの構造体
typedef struct Stack {
    Node* top; // スタックのトップを指すポインタ
} Stack;
// スタックの初期化
void initStack(Stack* stack) {
    stack->top = NULL;
}
// スタックにプッシュ
void push(Stack* stack, double value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
}
// スタックからポップ
double pop(Stack* stack) {
    if (stack->top == NULL) {
        printf("スタックが空です。\n");
        exit(EXIT_FAILURE);
    }
    Node* temp = stack->top;
    double value = temp->data;
    stack->top = stack->top->next;
    free(temp);
    return value;
}

ノードの定義

ノードはスタックの各要素を表します。

Node構造体は、データ部分と次のノードへのポインタを持ちます。

関数の設計

逆ポーランド記法の計算を行うために、入力の処理、演算子の評価、結果の出力を行う関数を設計します。

入力の処理

入力された逆ポーランド記法の数式をトークンに分割し、スタックにプッシュします。

以下は、入力を処理する関数の例です。

void processInput(Stack* stack, const char* input) {
    char* token = strtok(input, " ");
    while (token != NULL) {
        if (isdigit(token[0])) {
            push(stack, atof(token));
        } else {
            // 演算子の場合は後で処理
        }
        token = strtok(NULL, " ");
    }
}

演算子の評価

演算子が現れた場合、スタックからオペランドをポップし、計算を行います。

以下は、演算子を評価する関数の例です。

void evaluateOperator(Stack* stack, char operator) {
    double b = pop(stack);
    double a = pop(stack);
    double result;
    switch (operator) {
        case '+': result = a + b; break;
        case '-': result = a - b; break;
        case '*': result = a * b; break;
        case '/': result = a / b; break;
        default:
            printf("不正な演算子です。\n");
            exit(EXIT_FAILURE);
    }
    push(stack, result);
}

結果の出力

計算が完了したら、スタックのトップに残っている値が結果です。

これを出力します。

void printResult(Stack* stack) {
    if (stack->top != NULL) {
        printf("計算結果: %f\n", pop(stack));
    } else {
        printf("計算結果がありません。\n");
    }
}

このように、C言語で逆ポーランド記法を計算するプログラムを設計する際には、スタックを用いたデータ構造と関数を適切に組み合わせることが重要です。

完成したプログラム

ここでは、逆ポーランド記法を用いて数式を計算するC言語のプログラムを紹介します。

このプログラムは、スタックを用いて数式を評価し、結果を出力します。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
// ノードの構造体
typedef struct Node {
    double data; // データ部分
    struct Node* next; // 次のノードへのポインタ
} Node;
// スタックの構造体
typedef struct Stack {
    Node* top; // スタックのトップを指すポインタ
} Stack;
// スタックの初期化
void initStack(Stack* stack) {
    stack->top = NULL;
}
// スタックにプッシュ
void push(Stack* stack, double value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
}
// スタックからポップ
double pop(Stack* stack) {
    if (stack->top == NULL) {
        printf("スタックが空です。\n");
        exit(EXIT_FAILURE);
    }
    Node* temp = stack->top;
    double value = temp->data;
    stack->top = stack->top->next;
    free(temp);
    return value;
}
// 入力の処理
void processInput(Stack* stack, const char* input) {
    char* token = strtok(input, " ");
    while (token != NULL) {
        if (isdigit(token[0])) {
            push(stack, atof(token));
        } else {
            evaluateOperator(stack, token[0]);
        }
        token = strtok(NULL, " ");
    }
}
// 演算子の評価
void evaluateOperator(Stack* stack, char operator) {
    double b = pop(stack);
    double a = pop(stack);
    double result;
    switch (operator) {
        case '+': result = a + b; break;
        case '-': result = a - b; break;
        case '*': result = a * b; break;
        case '/': result = a / b; break;
        default:
            printf("不正な演算子です。\n");
            exit(EXIT_FAILURE);
    }
    push(stack, result);
}
// 結果の出力
void printResult(Stack* stack) {
    if (stack->top != NULL) {
        printf("計算結果: %f\n", pop(stack));
    } else {
        printf("計算結果がありません。\n");
    }
}
int main() {
    Stack stack;
    initStack(&stack);
    // 逆ポーランド記法の数式
    char input[] = "3 4 + 2 * 7 /";
    processInput(&stack, input);
    printResult(&stack);
    return 0;
}

実行例

計算結果: 2.000000

このプログラムは、逆ポーランド記法で表現された数式を入力として受け取り、スタックを用いて計算を行います。

main関数内で、数式を文字列として定義し、processInput関数でトークンに分割して処理します。

演算子が現れた場合はevaluateOperator関数で計算を行い、最終的な結果をprintResult関数で出力します。

応用例

逆ポーランド記法を用いた計算は、基本的な四則演算だけでなく、より複雑な数式や変数を含む計算にも応用できます。

ここでは、いくつかの応用例を紹介します。

複雑な数式の計算

逆ポーランド記法は、複雑な数式の計算にも適しています。

例えば、以下のような数式を考えます。

(3 + 4) * (5 - 2) / 7

この数式を逆ポーランド記法に変換すると、次のようになります。

3 4 + 5 2 - * 7 /

このように、逆ポーランド記法を用いることで、括弧を使わずに計算の順序を明確にできます。

プログラムは、スタックを用いてこの数式を効率的に計算します。

変数を用いた計算

逆ポーランド記法を用いた計算では、変数を扱うことも可能です。

変数を用いる場合、変数の値を事前に定義し、数式の中でその値を使用します。

以下に、変数を用いた計算の例を示します。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
// 変数の値を取得する関数
double getVariableValue(char variable) {
    switch (variable) {
        case 'x': return 5.0;
        case 'y': return 3.0;
        default:
            printf("不正な変数です。\n");
            exit(EXIT_FAILURE);
    }
}
// 入力の処理(変数対応版)
void processInputWithVariables(Stack* stack, const char* input) {
    char* token = strtok(input, " ");
    while (token != NULL) {
        if (isdigit(token[0])) {
            push(stack, atof(token));
        } else if (isalpha(token[0])) {
            push(stack, getVariableValue(token[0]));
        } else {
            evaluateOperator(stack, token[0]);
        }
        token = strtok(NULL, " ");
    }
}