C++ 프로그램에서 역 폴란드 표기법 평가

Reverse Polish 표기법이 있고 값을 평가해야 한다고 가정합니다. 역 폴란드어 표기법은 후위 표현이라고도 합니다. 여기서 우리는 접미사 표현식을 풀기 위해 스택 데이터 구조를 사용해야 합니다.

접미사 식에서 일부 피연산자가 발견되면 스택에 푸시합니다. 어떤 연산자가 발견되면 스택에서 두 개의 항목을 팝한 다음 올바른 순서로 작업을 수행합니다. 그 후 결과도 나중에 사용할 수 있도록 스택에 푸시됩니다. 전체 표현식을 완료한 후 최종 결과도 스택 상단에 저장됩니다. 따라서 표현식이 "53+62/*35*+"이면 답은 39가 됩니다.

단계를 살펴보겠습니다 -

• 접미사 식의 각 문자 ch에 대해 do
  • ch가 ☉ 연산자이면
    • a :=스택에서 첫 번째 요소 팝,
    • b :=스택에서 두 번째 요소 팝
    • res :=b ☉ a
    • 스택에 res를 푸시
  • ch가 피연산자이면
    • 스택에 ch 추가
• 스택 상단의 반환 요소

예(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

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

입력

"53+62/*35*+"

출력

The result is: 39