C++でのプレフィックス式の評価

---

この記事では、プレフィックス式の評価について説明します。

プレフィックス式

この表記では、演算子はプレフィックスです。 オペランドに、つまり演算子はオペランドの前に書き込まれます。たとえば、 + ab 。これは、中置記法 a + bと同等です。 。プレフィックス表記は、ポーランド記法とも呼ばれます。 。

詳細については、

をご覧ください。

例：

* + 6 9-3 1

接頭辞式は、中置式よりも速く評価されます。また、接頭辞式には角かっこがないため、評価が速くなります。

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

プレフィックス式の評価には、スタックデータ構造が必要です。演算子をスタックにプッシュしてから、式を解きます。

式の各要素を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。

ソリューションの動作を説明するプログラム

例

#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