Chương trình đánh giá ký hiệu Postfix trong C ++

Giả sử chúng ta có biểu thức postfix và chúng ta phải đánh giá giá trị. Biểu thức hậu tố còn được gọi là ký hiệu đánh bóng ngược. Ở đây chúng ta phải sử dụng cấu trúc dữ liệu ngăn xếp để giải các biểu thức postfix.

Vì vậy, nếu biểu thức là “21 + 3 *”, thì câu trả lời sẽ là 9.

Hãy để chúng tôi xem các bước -

• đối với mỗi ký tự ch trong biểu thức hậu tố, hãy thực hiện
  • nếu ch là một toán tử $ \ odot $, thì
    • a:=bật phần tử đầu tiên từ ngăn xếp,
    • b:=pop phần tử thứ hai từ ngăn xếp
    • res:=b $ \ odot $ a
    • đẩy res vào ngăn xếp
  • else nếu ch là một toán hạng thì
    • thêm ch vào ngăn xếp
• trả về phần tử của đỉnh ngăn xếp

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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);
}

Đầu vào

"21+3*"

Đầu ra

9