Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 역폴란드 표기법(후위 표기법) 수식 평가하기 – 스택 활용 완벽 가이드

역폴란드 표기법(Reverse Polish Notation, RPN)은 후위 표기법(postfix expression)이라고도 불리는 수식 표현 방식입니다. 이 표기법은 연산자가 피연산자 뒤에 오는 특징이 있어, 괄호 없이도 연산 우선순위를 명확하게 나타낼 수 있습니다.

후위 표기법으로 작성된 수식의 값을 계산할 때는 스택(stack) 자료구조를 활용하는 것이 가장 효율적입니다. 계산 원리는 다음과 같습니다.

  • 수식을 왼쪽부터 읽다가 피연산자를 만나면 스택에 push합니다.
  • 연산자를 만나면 스택에서 두 개의 항목을 pop한 뒤, 올바른 순서로 연산을 수행합니다.
  • 연산 결과는 이후 계산에 사용하기 위해 다시 스택에 push합니다.
  • 전체 수식의 처리가 끝나면 최종 결과값이 스택의 top에 저장됩니다.

예를 들어 수식이 "53+62/*35*+"라면, 최종 결과는 39가 됩니다.

알고리즘 단계

  • 후위 표기식의 각 문자 ch에 대해 반복:
    • ch가 연산자 ☉인 경우
      • a := 스택에서 첫 번째 요소를 pop
      • b := 스택에서 두 번째 요소를 pop
      • res := b ☉ a
      • res를 스택에 push
    • ch가 피연산자인 경우
      • ch를 스택에 push
  • 스택의 top에 있는 요소를 반환

C++ 구현 예제

아래 코드를 통해 실제 동작 방식을 더 잘 이해할 수 있습니다.

#include<iostream>
#include<cmath>
#include<stack>
#include<climits>
using namespace std;
float scanNum(char ch){
   int value;
   value = ch;
   return float(value-'0');//문자를 숫자(float)로 변환하여 반환
}
int isOperator(char ch){
   if(ch == '+'|| ch == '-'|| ch == '*'|| ch == '/' || ch == '^')
      return 1;//연산자인 경우
   return -1;//연산자가 아닌 경우
}
int isOperand(char ch){
   if(ch >= '0' && ch <= '9')
      return 1;//피연산자인 경우
   return -1;//피연산자가 아닌 경우
}
float operation(int a, int b, char op){
   //실제 연산 수행
   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); //b^a 계산
   else
      return INT_MIN; //음의 무한대 반환
}
float postfixEval(string postfix){
   int a, b;
   stack<float> stk;
   string::iterator it;
   for(it=postfix.begin(); it!=postfix.end(); it++){
      //각 문자를 읽으며 후위 표기식 평가 수행
      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

예제 수식의 계산 과정 살펴보기

"53+62/*35*+"가 어떻게 39가 되는지 단계별로 확인해 보겠습니다.

  1. 5, 3 → 피연산자이므로 스택에 push → 스택: [5, 3]
  2. + → 3과 5를 pop하여 5+3=8 계산 후 push → 스택: [8]
  3. 6, 2 → push → 스택: [8, 6, 2]
  4. / → 2와 6을 pop하여 6/2=3 계산 후 push → 스택: [8, 3]
  5. * → 3과 8을 pop하여 8*3=24 계산 후 push → 스택: [24]
  6. 3, 5 → push → 스택: [24, 3, 5]
  7. * → 5와 3을 pop하여 3*5=15 계산 후 push → 스택: [24, 15]
  8. + → 15와 24를 pop하여 24+15=39 계산 후 push → 스택: [39]

최종적으로 스택에는 39만 남게 되며, 이것이 바로 수식의 결과값입니다. 이처럼 스택 기반 평가 방식은 중위 표기법을 후위 표기법으로 변환한 뒤 계산하는 컴파일러나 계산기 프로그램에서 널리 사용되는 핵심 기법입니다.