中置記法から後置記法への変換方法｜スタックを使ったアルゴリズムとC++実装例

中置記法（インフィックス記法）は、人間にとって読みやすく理解しやすい数式の表現形式です。私たちは演算子の優先順位を容易に判別できるうえ、括弧を使えば先に計算すべき部分を明示することもできます。

一方、コンピュータにとっては演算子や括弧の区別が簡単ではありません。そのため、計算機で効率よく処理するには後置記法（ポストフィックス記法）への変換が必要になります。

中置記法から後置記法への変換には、スタックというデータ構造を使用します。中置式を左から右へ走査しながら、オペランド（被演算子）を見つけたらそのまま後置式へ追加します。演算子や括弧が出てきた場合は、それぞれの優先順位を保ちながらスタックに積んでいきます。

注： 本記事では {+, −, *, /, ^} の5種類の演算子のみを対象とし、それ以外の演算子は扱いません。

入力と出力の例

入力：
中置式：x^y/(5*z)+2
出力：
後置式：xy^5z*/2+

アルゴリズム

infixToPostfix(infix)

入力： 中置式（infix expression）

出力： 後置形式に変換された式

Begin
    最初に特別な記号 # をスタックにプッシュしておく
    中置式の各文字 ch について繰り返し処理を行う
        もし ch が英数字ならば
            ch を後置式に追加する
        もし ch が開き括弧 ( ならば
            ( をスタックにプッシュする
        もし ch が ^ ならば              // 優先度の高いべき乗演算子
            ^ をスタックにプッシュする
        もし ch が閉じ括弧 ) ならば
            スタックが空でなく、かつスタックトップが ( でない間、
                スタックからポップして後置式に追加する
            繰り返し終了
            ( もスタックからポップして削除する
        上記以外の場合
            スタックが空でなく、かつ ch の優先度がスタックトップ要素以下である間、
                ポップして後置式に追加する
            繰り返し終了
            新しく読み込んだ文字をスタックにプッシュする
    繰り返し終了
    スタックに残っている文字がある間、
        ポップして後置式に追加する
    繰り返し終了
    後置式を返す
End

C++による実装例

#include<iostream>
#include<stack>
#include<locale>      // isalnum() 関数を使用するため
using namespace std;

int preced(char ch) {
    if(ch == '+' || ch == '-') {
        return 1;          // + または - の優先度は 1
    }else if(ch == '*' || ch == '/') {
        return 2;          // * または / の優先度は 2
    }else if(ch == '^') {
        return 3;          // ^ の優先度は 3
    }else {
        return 0;
    }
}

string inToPost(string infix) {
    stack<char> stk;
    stk.push('#');             // アンダーフロー防止のための番兵文字
    string postfix = "";       // 初期状態では後置式は空
    string::iterator it;

    for(it = infix.begin(); it != infix.end(); it++) {
        if(isalnum(char(*it)))
            postfix += *it;    // 英数字なら後置式へ追加
        else if(*it == '(')
            stk.push('(');
        else if(*it == '^')
            stk.push('^');
        else if(*it == ')') {
            while(stk.top() != '#' && stk.top() != '(') {
                postfix += stk.top(); // ( が見つかるまで格納してポップ
                stk.pop();
            }
            stk.pop();             // '(' をスタックから取り除く
        }else {
            if(preced(*it) > preced(stk.top()))
                stk.push(*it);     // 優先度が高ければプッシュ
            else {
                while(stk.top() != '#' && preced(*it) <= preced(stk.top())) {
                    postfix += stk.top();   // 高い優先度が見つかるまで格納してポップ
                    stk.pop();
                }
                stk.push(*it);
            }
        }
    }

    while(stk.top() != '#') {
        postfix += stk.top();      // スタックが空になるまで格納してポップ
        stk.pop();
    }

    return postfix;
}

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

実行結果

Postfix Form Is: xy^5z*/2+

このように、スタックを活用した一連の手順に従うことで、中置記法の数式を機械処理に適した後置記法へ正確に変換できます。後置記法は評価時に括弧や優先順位の考慮が不要になるため、コンパイラや電卓アプリなど幅広い場面で利用されています。