C++でスタックを使って後置記法（逆ポーランド記法）の式を評価する方法

数式をコンピュータで計算するには、中置記法ではなく前置記法（プレフィックス）または後置記法（ポストフィックス／逆ポーランド記法）の形式に変換するのが一般的です。中置記法から後置記法への変換が完了したら、次は後置記法の評価アルゴリズムを使って正しい答えを求めます。

この評価処理においても、重要な役割を果たすのがスタック（Stack）というデータ構造です。

後置記法の評価の基本的な考え方

後置記法の式を左から右へ読み進めながら、以下の手順で処理を行います。

• オペランド（数値）を見つけたら、スタックにプッシュします。
• 演算子を見つけたら、スタックから2つの要素をポップし、正しい順序で演算を実行します。
• 演算結果は、今後の計算に備えて再びスタックにプッシュします。

式全体の読み込みが完了すると、スタックのトップに最終結果が残ります。

入力：後置記法の式　53+62/*35*+
出力：結果　　　　　39

アルゴリズム

postfixEvaluation(postfix)

入力：評価対象となる後置記法の式

出力：後置記法の式を評価した答え

開始
　　後置記法の式内の各文字 ch に対して繰り返す：
　　　　もし ch が演算子ならば：
　　　　　　a := スタックから最初の要素をポップ
　　　　　　b := スタックから2番目の要素をポップ
　　　　　　res := b （演算子） a
　　　　　　res をスタックにプッシュ
　　　　そうでなく、もし ch がオペランドならば：
　　　　　　ch をスタックにプッシュ
　　繰り返し終了
　　スタックのトップにある要素を返す
終了

サンプルコード（C++）

#include<iostream>
#include<cmath>
#include<stack>
using namespace std;

// 文字を数値（float型）に変換して返す
float scanNum(char ch) {
    int value;
    value = ch;
    return float(value-'0');
}

// 文字が演算子かどうかを判定する
int isOperator(char ch) {
    if(ch == '+'|| ch == '-'|| ch == '*'|| ch == '/' || ch == '^')
        return 1;  // 演算子である
    return -1;     // 演算子ではない
}

// 文字がオペランド（数字）かどうかを判定する
int isOperand(char ch) {
    if(ch >= '0' && ch <= '9')
        return 1;  // オペランドである
    return -1;     // オペランドではない
}

// 実際の演算を実行する
float operation(int a, int b, char op) {
    if(op == '+')
        return b+a;
    else if(op == '-')
        return b-a;
    else if(op == '*')
        return b*a;
    else if(op == '/')
        return b/a;
    else if(op == '^')
        return pow(b,a);  // b の a 乗を計算
    else
        return INT_MIN;   // エラー時は負の無限大を返す
}

// 後置記法の式を評価する本体
float postfixEval(string postfix) {
    int a, b;
    stack<float> stk;
    string::iterator it;
    for(it=postfix.begin(); it!=postfix.end(); it++) {
        // 各文字を読み取り、後置記法の評価を実行
        if(isOperator(*it) != -1) {
            a = stk.top();
            stk.pop();
            b = stk.top();
            stk.pop();
            stk.push(operation(a, b, *it));
        }else if(isOperand(*it) > 0) {
            stk.push(scanNum(*it));
        }
    }
    return stk.top();
}

main() {
    string post = "53+62/*35*+";
    cout << "The result is: "<<postfixEval(post);
}

実行結果

The result is: 39

計算過程の解説

例として挙げた式 53+62/*35*+ がどのように評価されるのか、スタックの動きを追ってみましょう。

1. 5、3 をプッシュ → + を検出 → 5 + 3 = 8 をプッシュ
2. 6、2 をプッシュ → / を検出 → 6 ÷ 2 = 3 をプッシュ
3. * を検出 → 8 × 3 = 24 をプッシュ
4. 3、5 をプッシュ → * を検出 → 3 × 5 = 15 をプッシュ
5. + を検出 → 24 + 15 = 39 をプッシュ

このように、元の中置記法の式 (5+3)*(6/2)+3*5 と同じ結果である 39 が得られます。スタックを使うことで、括弧や演算子の優先順位を意識せずに、左から右へ機械的に処理できる点が後置記法評価の大きな利点です。