C++で逆ポーランド記法（後置記法）の式を評価する方法

本記事では、逆ポーランド記法（Reverse Polish Notation／後置記法）で書かれた数式をC++で評価する方法を解説します。逆ポーランド記法は、演算子をオペランドの後に置く記法で、括弧が不要になるためコンパイラや電卓プログラムなどで広く使われています。この種の式（後置式）を評価する際には、スタックというデータ構造を利用するのが定番のアプローチです。

評価の基本的な考え方

後置式を左から右へ読み進めながら、次のように処理を行います。

• オペランド（数値）が現れたら、スタックにプッシュする。
• 演算子が現れたら、スタックから2つの要素をポップし、正しい順序で演算を実行する。その結果を再びスタックにプッシュして、以降の計算に備える。

式全体の走査が完了すると、スタックの先頭に最終結果が残ります。例えば、式 53+62/*35*+ を評価すると、答えは 39 になります。

アルゴリズムの手順

• 後置式の各文字 ch に対して、以下を繰り返す。
  • ch が演算子 ☉ の場合
    • a := スタックから最初の要素をポップ
    • b := スタックから次の要素をポップ
    • res := b ☉ a
    • res をスタックにプッシュ
  • ch がオペランドの場合
    • ch をスタックにプッシュ
• 最後に、スタックの先頭要素を返す。

具体例：「53+62/*35*+」の計算過程

動きをイメージしやすくするため、式 53+62/*35*+ の処理を追ってみましょう。

• 5、3 をプッシュ → + で 5＋3＝8 をプッシュ
• 6、2 をプッシュ → / で 6÷2＝3 をプッシュ
• * で 8×3＝24 をプッシュ
• 3、5 をプッシュ → * で 3×5＝15 をプッシュ
• + で 24＋15＝39 がスタックの先頭に残る

C++での実装例

以下は、上記のアルゴリズムをC++で実装したコードです。

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

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

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);
}

入力

"53+62/*35*+"

出力

The result is: 39

まとめ

このように、スタックを使えば逆ポーランド記法の式を括弧や優先順位を意識することなく、線形時間 O(n) で簡潔に評価できます。各文字を一度だけ読み、オペランドならプッシュ、演算子ならポップして計算する――このシンプルな規則だけで任意の後置式を処理できるのが、このアルゴリズムの大きな魅力です。