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

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

前置記法と中置記法とは

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

一方、中置記法（インフィックス表記）は、演算子がオペランドとオペランドの間に置かれる、私たちが普段目にする一般的な数式の書き方です。
例：A+B

中置記法は人間にとって理解しやすい形式ですが、コンピュータは計算を行う際に前置記法や後置記法（ポストフィックス表記）を利用します。特に後置記法はスタックベースの評価に適しており、多くの処理系で採用されています。

問題例

入力：prefix : /+LM/NX
出力：infix : (L+M) / (N/X)

解決アプローチ：スタックを使った変換アルゴリズム

この問題を解くには、スタックというデータ構造を利用します。手順は以下の通りです。

1. 前置記法の式を末尾から先頭へ向かって逆順に走査します。
2. 各要素について次のように処理を分けます。

• 要素がオペランドの場合 → そのままスタックにプッシュします。
• 要素が演算子の場合 → スタックから2つの要素をポップし、「オペランド + 演算子 + オペランド」の順に連結した文字列を作成して、再びスタックにプッシュします。

走査が完了した時点で、スタックのトップに残っている文字列こそが、求める中置記法への変換結果となります。これを出力すれば完成です。

C++による実装例

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

// 演算子かどうかを判定する関数
bool isOperator(char element) {
    switch (element) {
        case '+':
        case '-':
        case '/':
        case '*':
            return true;
    }
    return false;
}

// 前置記法を中置記法へ変換する関数
string convertToInfix(string prefix) {
    stack<string> expression;
    int length = prefix.size();

    // 式を逆順に走査する
    for (int i = length - 1; i >= 0; i--) {
        if (isOperator(prefix[i])) {
            // 演算子なら2つのオペランドを取り出して結合
            string op1 = expression.top();
            expression.pop();
            string op2 = expression.top();
            expression.pop();
            string temp = "{" + op1 + prefix[i] + op2 + "}";
            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 << "Infix expression : " << convertToInfix(prefix);
    return 0;
}

実行結果

Prefix expression : *-AB/+CD*XY
Infix expression : {{A-B}*{{C+D}/{X*Y}}}

まとめ

このように、スタックを活用して前置記法の式を逆順に走査することで、シンプルな手順で中置記法への変換が実現できます。時間計算量は O(n)、空間計算量も O(n) であり、式の長さに対して線形で動作する効率的なアルゴリズムです。逆ポーランド記法との相互変換など、関連するトピックもあわせて学習すると理解が深まります。