C言語におけるスタックを使った後置記法（逆ポーランド記法）の式評価を解説

スタック（Stack）は線形データ構造の一種で、データの挿入と削除が必ず一端（トップ）からのみ行われるという特徴を持ちます。この「後入れ先出し（LIFO: Last In First Out）」の性質により、式の評価や構文解析など、さまざまな場面で活用されています。

基本アルゴリズム

Push（挿入）のアルゴリズム

まず、スタックオーバーフローが発生していないかを確認します。

if (top == n-1)
    printf("stack over flow");

オーバーフローしていない場合は、要素をスタックに挿入します。

top++
a[top] = item

Pop（削除）のアルゴリズム

まず、スタックアンダーフローが発生していないかを確認します。

if (top == -1)
    printf("stack under flow");

アンダーフローしていない場合は、スタックから要素を取り出します。

item = a[top]
top--

Display（表示）のアルゴリズム

スタックが空かどうかを確認します。

if (top == -1)
    printf("stack is empty");

要素がある場合は、以下のようにスタックの中身を表示します。

for (i=0; i<top; i++)
    printf("%d", a[i]);

スタックの応用：式の変換と評価

スタックは、数式の変換や評価において特に重要な役割を果たします。ここでは、C言語における式の変換について解説します。

式（Expression）とは、オペランド（被演算子）と演算子を組み合わせた、文法的に正しい表現のことです。

式の3種類

C言語では、変換や評価の対象となる式には以下の3種類があります。

• 中置記法（Infix）：演算子がオペランドの間に置かれます。例：A+B
• 前置記法（Prefix）：演算子がオペランドの前に置かれます。例：+AB
• 後置記法（Postfix）：演算子がオペランドの後に置かれます。例：AB+

コンピュータは後置記法（逆ポーランド記法とも呼ばれます）を最も効率的に処理できるため、スタックを使った後置記法の評価が広く用いられています。

後置記法の式の評価方法

アルゴリズム

入力文字列を左から右へ走査します。各入力記号に対して、以下の処理を行います。

• 数字であれば、スタックにプッシュします。
• 演算子であれば、スタックから上位2つの値をポップし、その演算子を適用します。その後、計算結果をスタックにプッシュします。
• 入力記号が'\0'（文字列の終端）であれば、スタックを空にして処理を終了します。

評価の流れの例：「45+」の場合

1. '4'は数字なのでスタックにプッシュ → スタック：[4]
2. '5'は数字なのでスタックにプッシュ → スタック：[4, 5]
3. '+'は演算子なので、5と4をポップして加算 → 4+5=9
4. 結果の9をスタックにプッシュ → スタック：[9]
5. 文字列の終端に到達したので、スタックから9を取り出して結果として出力

サンプルプログラム

以下は、後置記法の式を評価するCプログラムです。

#include<stdio.h>
int top = -1, stack[100];
main() {
    char a[50], ch;
    int i, op1, op2, res, x;
    void push(int);
    int pop();
    int eval(char, int, int);
    printf("enter a postfix expression:");
    gets(a);
    for (i = 0; a[i] != '\0'; i++) {
        ch = a[i];
        if (ch >= '0' && ch <= '9')
            push(ch - '0');   /* 文字を数値に変換してプッシュ */
        else {
            op2 = pop();
            op1 = pop();
            res = eval(ch, op1, op2);
            push(res);
        }
    }
    x = pop();
    printf("evaluated value = %d", x);
    getch();
}
void push(int n) {
    top++;
    stack[top] = n;
}
int pop() {
    int res;
    res = stack[top];
    top--;
    return res;
}
int eval(char ch, int op1, int op2) {
    switch (ch) {
        case '+': return (op1 + op2);
        case '-': return (op1 - op2);
        case '*': return (op1 * op2);
        case '/': return (op1 / op2);
    }
}

なお、gets()関数はバッファオーバーフローの危険性があるため、現在では非推奨とされています。実際の開発では、fgets()やscanf()の使用を検討してください。

実行結果

上記のプログラムを実行すると、以下のような結果が得られます。

Run 1:
enter a postfix expression:45+
evaluated value = 9
Run 2:
enter a postfix expression: 3 5 2 * +
evaluated value = 13

Run 2の「3 5 2 * +」は、中置記法でいう「3 + (5 × 2)」に相当し、計算結果は13になります。このように、スタックを使えば括弧を含む複雑な式も、後置記法に変換することで簡単かつ効率的に評価できます。