C++でプレフィックス式（前置記法）を評価する方法

この記事では、プレフィックス式（前置記法）の評価方法について詳しく解説します。

プレフィックス式とは

プレフィックス記法では、演算子がオペランドの前に置かれるのが特徴です。つまり、演算子がオペランドよりも先に書かれます。例えば「+ab」は、中置記法の「a + b」と同じ意味を持ちます。プレフィックス記法は「ポーランド記法」とも呼ばれています。

例：

* + 6 9 - 3 1

プレフィックス式は中置式よりも高速に評価できるという利点があります。また、括弧が一切不要なため、評価処理をより素早く行うことができます。

プレフィックス式を評価するアルゴリズム

プレフィックス式の評価にはスタックというデータ構造を使用します。式の要素を順番にスタックへプッシュしながら、演算を進めていきます。

式の各要素を一つずつ走査していきます。現在の要素がオペランドであればスタックにプッシュし、演算子であればスタックから2つのオペランドをポップして「オペランド 演算子 オペランド」の形で演算を実行し、その結果を再びスタックにプッシュします。

アルゴリズムの手順

ステップ1： 式の最後の要素から処理を開始します。

ステップ2： 現在の要素を確認します。

ステップ2.1： オペランドであれば、スタックにプッシュします。
ステップ2.2： 演算子であれば、スタックから2つのオペランドをポップします。演算を実行し、結果をスタックに戻します。

ステップ3： 式のすべての要素を走査し終えたら、スタックのトップ（先頭）にある値を返します。これが演算結果となります。

アルゴリズムの動作例

それでは、実際のプレフィックス式を使ってアルゴリズムの動作を確認してみましょう。

プレフィックス式：

* + 6 9 - 3 1

反復1：

走査した要素 => 1
操作 => スタックにプッシュ
スタック => 1

反復2：

走査した要素 => 3
操作 => スタックにプッシュ
スタック => 3, 1

反復3：

走査した要素 => -
操作 => スタックから2つポップし、演算を実行して結果をプッシュ
3 - 1 = 2
スタック => 2

反復4：

走査した要素 => 9
操作 => スタックにプッシュ
スタック => 9, 2

反復5：

走査した要素 => 6
操作 => スタックにプッシュ
スタック => 6, 9, 2

反復6：

走査した要素 => +
操作 => スタックから2つポップし、演算を実行して結果をプッシュ
6 + 9 = 15
スタック => 15, 2

反復7：

走査した要素 => *
操作 => スタックから2つポップし、演算を実行して結果をプッシュ
15 * 2 = 30
スタック => 30

終了 => スタックのトップを返す。結果 = 30

ソリューションの動作を示すサンプルプログラム

C++コード例

#include <bits/stdc++.h>
using namespace std;

double evaluatePrefix(string prefixExp) {
    
    stack<double> operendStack;
    int size = prefixExp.size() - 1;
    
    for (int i = size; i >= 0; i--) {

       if (isdigit(prefixExp[i]))
          operendStack.push(prefixExp[i] - '0');
       else {
          double o1 = operendStack.top();
          operendStack.pop();
          double o2 = operendStack.top();
          operendStack.pop();
          if( prefixExp[i] == '+')
             operendStack.push(o1 + o2);
          else if( prefixExp[i] == '-')
             operendStack.push(o1 - o2);
          else if( prefixExp[i] == '*')
             operendStack.push(o1 * o2);
          else if( prefixExp[i] == '/')
             operendStack.push(o1 / o2);
          else{
             cout<<"Invalid Expression";
             return -1;
          }
       }
    }
    return operendStack.top();
}

int main()
{
    string prefixExp = "*+69-31";
    cout<<"The result of evaluation of expression "<<prefixExp<<" is "<<evaluatePrefix(prefixExp);
    return 0;
}

出力結果

The result of evaluation of expression *+69-31 is 30

このように、スタックを活用することで、プレフィックス式を右から左へ効率的に評価できます。演算子の優先順位や括弧を考慮する必要がないため、コンパイラや電卓アプリなどの実装でも広く利用されている手法です。