Đánh giá ký hiệu tiếng Ba Lan ngược trong Chương trình C ++

Giả sử chúng ta có ký hiệu Đánh bóng ngược và chúng ta phải đánh giá giá trị. Ký hiệu đánh bóng ngược còn được gọi là biểu thức hậu tố. Ở đâ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.

Từ biểu thức hậu tố, khi một số toán hạng được tìm thấy, hãy đẩy chúng vào ngăn xếp. Khi một số toán tử được tìm thấy, hai mục sẽ xuất hiện từ ngăn xếp và sau đó hoạt động được thực hiện theo đúng trình tự. Sau đó, kết quả cũng được đẩy vào ngăn xếp để sử dụng trong tương lai. Sau khi hoàn thành toàn bộ biểu thức, kết quả cuối cùng cũng được lưu trữ trong ngăn xếp. Vì vậy, nếu biểu thức là “53 + 62 / * 35 * +”, thì câu trả lời sẽ là 39

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ử ☉, 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 ☉ 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

Ví dụ (C ++)

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

#include<iostream>
#include<cmath>
#include<stack>
#include<climits>
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 = "53+62/*35*+";
   cout << "The result is: "<<postfixEval(post);
}

Đầu vào

"53+62/*35*+"

Đầu ra

The result is: 39