중위 표기식을 후위 표기식으로 변환하는 방법

중위 표기법(infix notation)은 사람이 읽고 이해하기 가장 자연스러운 수식 표현 방식입니다. 연산자의 우선순위를 쉽게 파악할 수 있고, 괄호를 사용해 계산 순서를 명확하게 지정할 수도 있습니다. 반면 컴퓨터는 연산자와 괄호를 사람처럼 직관적으로 판단하지 못하기 때문에, 수식을 효율적으로 처리하려면 후위 표기법(postfix notation)으로 변환하는 과정이 필요합니다.

중위 표기식을 후위 표기식으로 변환할 때는 스택(stack) 자료구조를 활용합니다. 식을 왼쪽에서 오른쪽으로 한 문자씩 스캔하면서 피연산자(operand)를 만나면 곧바로 후위 표기식에 추가하고, 연산자나 괄호를 만나면 우선순위 규칙에 따라 스택에 push합니다.

참고: 여기서는 {+, −, *, /, ^} 연산자만 다루며, 그 외의 연산자는 고려하지 않습니다.

입력과 출력

입력:
중위 표기식: x^y/(5*z)+2
출력:
후위 표기식: xy^5z*/2+

알고리즘

입력: 중위 표기식

출력: 후위 표기식으로 변환된 결과

시작
    스택에 특수 문자 '#'를 먼저 push (언더플로 방지용)
    중위 표기식의 각 문자 ch에 대해 반복:
        ch가 알파벳 또는 숫자이면
            ch를 후위 표기식에 추가
        아니고 ch가 여는 괄호 '('이면
            '('를 스택에 push
        아니고 ch가 '^'이면          // 우선순위가 가장 높은 거듭제곱 연산자
            '^'를 스택에 push
        아니고 ch가 닫는 괄호 ')'이면
            스택이 비어 있지 않고 스택 top이 '('가 아닐 동안
                스택에서 pop한 항목을 후위 표기식에 추가
            '('도 스택에서 pop하여 제거
        그 외의 경우(연산자)
            스택이 비어 있지 않고 ch의 우선순위 ≤ 스택 top 요소의 우선순위인 동안
                pop한 항목을 후위 표기식에 추가
            새로 들어온 문자를 스택에 push
    스택에 남은 문자가 있는 동안
        pop한 항목을 후위 표기식에 추가
    후위 표기식 반환
끝

C++ 구현 예제

#include<iostream>
#include<stack>
#include<locale>      //isalnum() 함수 사용을 위한 헤더
using namespace std;

int preced(char ch) {
   if(ch == '+' || ch == '-') {
      return 1;             // + 또는 - 의 우선순위는 1
   }else if(ch == '*' || ch == '/') {
      return 2;             // * 또는 / 의 우선순위는 2
   }else if(ch == '^') {
      return 3;             // ^ 의 우선순위는 3
   }else {
      return 0;
   }
}

string inToPost(string infix ) {
   stack<char> stk;
   stk.push('#');               // 언더플로 방지를 위한 추가 문자 삽입
   string postfix = "";         // 초기 후위 표기식은 빈 문자열
   string::iterator it;

   for(it = infix.begin(); it!=infix.end(); it++) {
      if(isalnum(char(*it)))
         postfix += *it;        // 문자나 숫자이면 후위 표기식에 추가
      else if(*it == '(')
         stk.push('(');
      else if(*it == '^')
         stk.push('^');
      else if(*it == ')') {
         while(stk.top() != '#' && stk.top() != '(') {
            postfix += stk.top(); // '('를 찾을 때까지 저장 후 pop
            stk.pop();
         }
         stk.pop();              // 스택에서 '(' 제거
      }else {
         if(preced(*it) > preced(stk.top()))
            stk.push(*it);       // 우선순위가 더 높으면 push
         else {
            while(stk.top() != '#' && preced(*it) <= preced(stk.top())) {
               postfix += stk.top();        // 더 높은 우선순위를 찾을 때까지 저장 후 pop
               stk.pop();
            }
            stk.push(*it);
         }
      }
   }

   while(stk.top() != '#') {
      postfix += stk.top();     // 스택이 빌 때까지 저장 후 pop
      stk.pop();
   }

   return postfix;
}

int main() {
   string infix = "x^y/(5*z)+2";
   cout << "Postfix Form Is: " << inToPost(infix) << endl;
}

실행 결과

Postfix Form Is: xy^5z*/2+

변환된 후위 표기식에는 괄호가 포함되지 않으며, 연산자의 우선순위가 이미 식의 배치 순서에 반영되어 있습니다. 이러한 특성 덕분에 컴퓨터는 스택 하나만으로 후위 표기식을 왼쪽부터 차례대로 빠르고 정확하게 계산할 수 있습니다.