中置記法の式を前置記法（プレフィックス記法）へ変換する方法

コンピュータで数式を処理・評価する場合、式を後置記法（ポーランド逆記法）か前置記法（ポーランド記法）のどちらかに変換しておくのが一般的です。この記事では、私たちが普段使う中置記法（インフィックス記法）の式を、前置記法へ変換する手順を詳しく解説します。

前置記法への変換の基本の流れ

変換は大きく分けて次の3ステップで行います。

1. 式を反転する … 中置記法の式全体を逆順に並べ替えます。このとき、開き括弧「(」と閉じ括弧「)」も一緒に反転されてしまう点に注意が必要です。
2. 後置記法に変換する … 反転した式の括弧を正しい向きに修正してから、通常の「中置記法→後置記法」変換アルゴリズムで処理します。
3. 結果を再び反転する … 得られた後置記法の式を逆順に並べ替えると、目的の前置記法の式が完成します。

例として、式「A + B * (C - D)」を考えてみましょう。これを単純に反転すると「) D - C ( * B + A」となり、括弧の向きが逆になってしまいます。そこで、開き括弧を閉じ括弧へ、閉じ括弧を開き括弧へと入れ替えてから変換を行います。

入力と出力

入力:
中置記法の式: x^y/(5*z)+2
出力:
前置記法の式: +/^xy*5z2

アルゴリズム

infixToPrefix(infix)

入力 − 前置記法へ変換したい中置記法の式。

出力 − 変換結果となる前置記法の式。

Begin
   中置記法の式を反転する
   反転した式の各文字 ch について繰り返す
      もし ch が開き括弧ならば
         ch を閉じ括弧に変換する
      そうでなければ、もし ch が閉じ括弧ならば
         ch を開き括弧に変換する
   繰り返し終了

   postfix := 変換後の中置記法の式を後置記法へ変換した結果
   prefix := 先ほど求めた後置記法の式を反転した結果
   prefix を返す
End

C++による実装例

以下は、上記のアルゴリズムをC++で実装したサンプルコードです。演算子の優先順位は関数 preced() で定義しており、「+」「−」が優先度1、「*」「/」が優先度2、「^」（べき乗）が優先度3となっています。

#include<iostream>
#include<stack>
#include<locale> //for function isalnum()
#include<algorithm>
using namespace std;

int preced(char ch) {
   if(ch == '+' || ch == '-') {
      return 1;    //Precedence of + or - is 1
   }else if(ch == '*' || ch == '/') {
      return 2;    //Precedence of * or / is 2
   }else if(ch == '^') {
      return 3;    //Precedence of ^ is 3
   }else {
      return 0;
   }
}

string inToPost(string infix) {
   stack<char> stk;
   stk.push('#');    //add some extra character to avoid underflow
   string postfix = "";   //initially the postfix string is empty
   string::iterator it;

   for(it = infix.begin(); it!=infix.end(); it++) {
      if(isalnum(char(*it)))
         postfix += *it;    //add to postfix when character is letter or number
      else if(*it == '(')
         stk.push('(');
      else if(*it == '^')
         stk.push('^');
      else if(*it == ')') {
         while(stk.top() != '#' && stk.top() != '(') {
            postfix += stk.top();    //store and pop until ( has found
            stk.pop();
         }

         stk.pop();    //remove the '(' from stack
      }else {
         if(preced(*it) > preced(stk.top()))
            stk.push(*it);    //push if precedence is high
         else {
            while(stk.top() != '#' && preced(*it) <= preced(stk.top())) {
               postfix += stk.top();    //store and pop until higher precedence is found
               stk.pop();
            }
            stk.push(*it);
         }
      }
   }

   while(stk.top() != '#') {
      postfix += stk.top();    //store and pop until stack is not empty

      stk.pop();

   }
   return postfix;
}

string inToPre(string infix) {
   string prefix;
   reverse(infix.begin(), infix.end());    //reverse the infix expression
   string::iterator it;

   for(it = infix.begin(); it != infix.end(); it++) {    //reverse the parenthesis after reverse
      if(*it == '(')
         *it = ')';
      else if(*it == ')')
         *it = '(';
   }

   prefix = inToPost(infix);                 //convert new reversed infix to postfix form.
   reverse(prefix.begin(), prefix.end());    //again reverse the result to get final prefix form
   return prefix;
}

int main() {
   string infix = "x^y/(5*z)+2";
   cout << "Prefix Form Is: " << inToPre(infix) << endl;
}

実装のポイント

• スタックの底に番兵を設置 … スタックには最初に「#」を積んでおき、空スタックの参照（アンダーフロー）を防いでいます。
• 英数字はそのまま出力 … 文字や数字はオペランドなので、スタックを使わず直接後置表現へ追加します。
• べき乗「^」の特別扱い … べき乗演算子は右結合であるため、優先順位の比較を行わず常にスタックに積むよう処理されています。
• 括弧の処理 … 閉じ括弧「)」が出現したら、対応する開き括弧「(」が見つかるまでスタックから演算子を取り出して出力に追加します。

実行結果

Prefix Form Is: +/^xy*5z2