C++で後置記法を評価するプログラム

接尾辞式があり、値を評価する必要があるとします。後置式は、逆ポーランド記法とも呼ばれます。ここでは、スタックデータ構造を使用して接尾辞式を解決する必要があります。

したがって、式が「21 + 3 *」の場合、答えは9になります。

手順を見てみましょう-

• 後置式の文字chごとに、
  を実行します。
  • chが演算子$\odot $の場合、
    • a：=スタックから最初の要素をポップします
    • b：=スタックから2番目の要素をポップします
    • res：=b $ \ odot $ a
    • 解像度をスタックにプッシュします
  • それ以外の場合、chがオペランドの場合、
    • スタックにchを追加
• スタックトップの要素を返す

理解を深めるために、次の実装を見てみましょう-

例

#include<bits/stdc++.h>
using namespace std;
float scanNum(char ch){
   int value;
   value = ch;
   return float(value-'0');//return float from character
}
int isOperator(char ch){
   if(ch == '+'|| ch == '-'|| ch == '*'|| ch == '/' || ch == '^')
      return 1;//character is an operator
      return -1;//not an operator
   }
   int isOperand(char ch){
      if(ch >= '0' && ch <= '9')
         return 1;//character is an operand
      return -1;//not an operand
   }
   float operation(int a, int b, char op){
      //Perform operation
      if(op == '+')
         return b+a;
      else if(op == '-')
         return b-a;
      else if(op == '*')
         return b*a;
      else if(op == '/')
         return b/a;
      else if(op == '^')
         return pow(b,a); //find b^a
      else
   return INT_MIN; //return negative infinity
}
float postfixEval(string postfix){
   int a, b;
   stack<float> stk;
   string::iterator it;
   for(it=postfix.begin(); it!=postfix.end(); it++){
      //read elements and perform postfix evaluation
      if(isOperator(*it) != -1){
         a = stk.top();
         stk.pop();
         b = stk.top();
         stk.pop();
         stk.push(operation(a, b, *it));
      }else if(isOperand(*it) > 0){
         stk.push(scanNum(*it));
      }
   }
   return stk.top();
}
main(){
   string post = "21+3*";
   cout <<postfixEval(post);
}

入力

"21+3*"

出力

9