C++で前置記法（プレフィックス）から後置記法（ポストフィックス）へ変換する方法

この問題では、前置記法（プレフィックス）で表された式が与えられ、それを後置記法（ポストフィックス）に変換して出力することが求められます。

前置記法と後置記法とは

前置記法（プレフィックス記法）は、演算子がオペランド（被演算子）の前に置かれる表記方法です。

例：+AB

後置記法（ポストフィックス記法）は、演算子がオペランドの後に置かれる表記方法です。

例：AB+

なお、この変換処理では、中置記法（インフィックス）を経由せずに、直接前置記法から後置記法へ変換する必要があります。

問題例

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

入力：/+XY+NM
出力：XY+NM+/
説明：中置記法に直すと (X+Y)/(N+M)

解決アプローチ

この問題を解くには、まず前置記法の式全体を逆順（右から左）に走査します。そして、処理にはスタックというデータ構造を使用します。走査中に見つかった要素ごとに、以下のように処理を行います。

• オペランドの場合：スタックに要素をプッシュ（push）します。
• 演算子の場合：スタックから要素を2回ポップ（pop）し、「オペランド1 + オペランド2 + 演算子」の順序で連結した文字列を作成して、再びスタックにプッシュします。

すべての走査が完了した時点で、スタックの最上位にある文字列が求める後置記法の式となります。

C++での実装例

上記のアルゴリズムを実装したプログラムが以下の通りです。

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

bool isOperator(char x) {
    switch (x) {
        case '+':
        case '-':
        case '/':
        case '*':
            return true;
    }
    return false;
}

string convertToPostfix(string prefix) {
    stack<string> expression;
    int length = prefix.size();
    for (int i = length - 1; i >= 0; i--) {
        if (isOperator(prefix[i])) {
            string op1 = expression.top();
            expression.pop();
            string op2 = expression.top();
            expression.pop();
            string temp = op1 + op2 + prefix[i];
            expression.push(temp);
        }
        else
            expression.push(string(1, prefix[i]));
    }
    return expression.top();
}

int main() {
    string prefix = "*-AB/+CD*XY";
    cout << "Prefix expression : " << prefix << endl;
    cout << "Postfix expression : " << convertToPostfix(prefix);
    return 0;
}

実行結果

Prefix expression : *-AB/+CD*XY
Postfix expression : AB-CD+XY*/*

まとめ

このように、式を逆順に走査しながらスタックを操作することで、中置記法を経由することなく、前置記法から後置記法へ効率的に変換できます。時間計算量はO(n)、空間計算量もO(n)であり、非常にシンプルかつ実用的なアルゴリズムです。