접미사 표현식 평가

수학적 표현을 풀기 위해서는 접두사 또는 접미사 형식이 필요합니다. 중위를 후위로 변환한 후 정답을 찾기 위해서는 후위 평가 알고리즘이 필요합니다.

여기에서도 스택 데이터 구조를 사용하여 접미사 식을 해결해야 합니다.

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

입력 및 출력

Input:
Postfix expression: 53+62/*35*+
Output:
The result is: 39

알고리즘

postfixEvaluation(postfix)

입력: 평가할 접미사 표현식입니다.

출력: 접미사 형식을 평가한 후 응답하십시오.

Begin
   for each character ch in the postfix expression, do
      if ch is an operator ⨀ , then
         a := pop first element from stack
         b := pop second element from the stack
         res := b ⨀ a
         push res into the stack
      else if ch is an operand, then
         add ch into the stack
   done
   return element of stack top
End

예시

#include<iostream>
#include<cmath>
#include<stack>
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);
}

출력

The result is: 39