후위 표기식(포스트픽스) 평가 알고리즘 – 스택으로 간단하게 계산하기

수학적 표현식을 컴퓨터로 계산하려면 전위 표기법(prefix) 또는 후위 표기법(postfix) 형태로 바꾸는 것이 효율적입니다. 중위 표기식(infix)을 후위 표기식으로 변환한 뒤에는, 정확한 결과를 얻기 위해 후위 표기식 평가(postfix evaluation) 알고리즘이 필요합니다.

후위 표기식을 평가할 때에도 스택(Stack) 자료구조를 활용합니다. 기본 동작 원리는 다음과 같습니다.

• 표현식을 왼쪽에서 오른쪽으로 한 글자씩 읽습니다.
• 피연산자(숫자)를 만나면 스택에 push합니다.
• 연산자를 만나면 스택에서 두 개의 값을 pop하고, 올바른 순서로 연산을 수행한 뒤 그 결과를 다시 스택에 push합니다.
• 모든 문자를 처리하고 나면 스택의 top에 최종 결과가 남습니다.

입력 및 출력

입력:
후위 표기식: 53+62/*35*+

출력:
계산 결과: 39

평가 알고리즘

postfixEvaluation(postfix)

입력: 평가할 후위 표기식

출력: 후위 표기식을 계산한 결과값

시작
   후위 표기식의 각 문자 ch에 대해 반복:
      만약 ch가 연산자 ⨀이면
         a := 스택에서 첫 번째 요소를 pop
         b := 스택에서 두 번째 요소를 pop
         res := b ⨀ a
         res를 스택에 push
      아니면 ch가 피연산자이면
         ch를 스택에 push
   반복 종료
   스택 top의 요소를 반환
끝

C++ 구현 예제

다음은 위 알고리즘을 C++로 구현한 전체 코드입니다.

#include<iostream>
#include<cmath>
#include<stack>
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*+는 중위 표기식으로 ((5+3)*(6/2))+(3*5)에 해당하며, 스택의 변화는 다음과 같습니다.

1. 5, 3 push → 스택: [5, 3]
2. '+' 연산자 → 5+3=8 push → 스택: [8]
3. 6, 2 push → 스택: [8, 6, 2]
4. '/' 연산자 → 6÷2=3 push → 스택: [8, 3]
5. '*' 연산자 → 8×3=24 push → 스택: [24]
6. 3, 5 push → 스택: [24, 3, 5]
7. '*' 연산자 → 3×5=15 push → 스택: [24, 15]
8. '+' 연산자 → 24+15=39 push → 스택: [39]

따라서 최종 결과는 39입니다.

복잡도 분석

이 알고리즘은 표현식을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 또한 모든 피연산자를 스택에 저장해야 하므로 공간 복잡도 역시 O(n)입니다.

실행 결과

The result is: 39