C++에서 후위 표기법을 평가하는 프로그램

접미사 표현식이 있고 값을 평가해야 한다고 가정합니다. 후위 표현은 역 광택 표기법으로도 알려져 있습니다. 여기서 우리는 접미사 표현식을 풀기 위해 스택 데이터 구조를 사용해야 합니다.

따라서 표현식이 "21+3*"이면 답은 9가 됩니다.

단계를 살펴보겠습니다 -

• 접미사 식의 각 문자 ch에 대해 do
  • ch가 $\odot$ 연산자이면
    • a :=스택에서 첫 번째 요소 팝,
    • b :=스택에서 두 번째 요소 팝
    • res :=b $\odot$ a
    • 스택에 res를 푸시
  • 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