C++で後置記法（ポストフィックス）を中置記法（インフィックス）に変換する方法

問題の概要

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

中置記法とは、演算子がオペランド（被演算子）の間に配置される記法で、「オペランド 演算子 オペランド」という形になります。

後置記法とは、演算子がオペランドの後に配置される記法です。

後置記法はコンピュータにとって計算処理が容易である一方、人間にとっては読みづらいという特徴があります。そのため、このような変換処理が必要となります。一般的に、ユーザーによる数式の読み書きや編集は、括弧によって構造が明確になり理解しやすい中置記法で行われています。

問題例

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

入力 − xyz/*

出力 − (x * (y/z))

解決アプローチ

この問題を解くには、スタック（stack）データ構造を利用します。後置記法の式を先頭から1文字ずつ走査し、以下のいずれかのケースに応じて処理を行います。

ケース1 − 文字がオペランド（英字）の場合、そのままスタックにプッシュします。

ケース2 − 文字が演算子の場合、スタックから2つのオペランドをポップし、それらと演算子を組み合わせた中置記法の式を作成して、新たなオペランドとしてスタックにプッシュします。

すべての文字の走査が終了し、スタックに要素が1つだけ残ったら、その先頭要素をポップします。これが中置記法へ変換された式となります。このアルゴリズムの計算量は、式の長さをnとすると時間O(n)、空間O(n)で効率的に動作します。

C++実装例

上記の解法を実装したプログラムがこちらです。

#include <bits/stdc++.h>
using namespace std;
// オペランド（英字）かどうかを判定する関数
bool isOperand(char x) {
   return (x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z');
}
// 後置記法を中置記法に変換する関数
string infixConversion(string postfix) {
   stack<string> infix;
   for (int i=0; postfix[i]!='\0'; i++) {
      // ケース1：オペランドならスタックにプッシュ
      if (isOperand(postfix[i])) {
         string op(1, postfix[i]);
         infix.push(op);
      } else {
         // ケース2：演算子なら2つのオペランドをポップして結合
         string op1 = infix.top();
         infix.pop();
         string op2 = infix.top();
         infix.pop();
         infix.push("{"+op2+postfix[i]+op1 +"}");
      }
   }
   return infix.top();
}
int main() {
   string postfix = "xyae+/%";
   cout<<"後置記法の式 '"<<postfix<<"' を中置記法に変換すると : ";
   cout<<infixConversion(postfix);
   return 0;
}

出力結果

後置記法の式 'xyae+/%' を中置記法に変換すると : {x%{y/{a+e}}}

まとめ

後置記法から中置記法への変換は、スタックを使うことでシンプルに実装できます。オペランドを積み上げていき、演算子が出現したタイミングで直近の2つのオペランドを取り出して結合する、という操作の繰り返しがポイントです。逆ポーランド記法とも呼ばれる後置記法は、電卓アプリやコンパイラの式評価などで広く使われているため、この変換手法は実務でも役立つ知識といえます。