C++로 접두사 표기식을 접미사 표기식으로 변환하는 방법

이 문제에서는 접두사(prefix) 표기식이 주어지며, 이를 접미사(postfix) 표기식으로 변환하여 출력하는 것이 목표입니다.

접두사와 접미사 표기법이란?

접두사 표기식은 연산자가 피연산자 앞에 위치하는 표현 방식입니다.

예시: +AB

접미사 표기식은 연산자가 피연산자 뒤에 위치하는 표현 방식입니다.

예시: AB/

이때 중요한 조건은 접두사를 접미사로 변환하는 과정에서 중위(infix) 표기식을 거치지 않고 직접 변환해야 한다는 점입니다.

문제 예시

입력: /+XY+NM
출력: XY+NM+/
설명: 중위 표기식 -> (X+Y)/(N+M)

해결 알고리즘

이 문제는 스택(stack) 자료구조를 활용하여 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

먼저 접두사 표현식을 오른쪽에서 왼쪽으로(역순으로) 순회하면서, 각 문자의 종류에 따라 아래와 같이 처리합니다.

피연산자인 경우: 해당 요소를 스택에 push합니다.
연산자인 경우: 스택에서 요소 두 개를 pop한 뒤, '피연산자 + 피연산자 + 연산자' 순서로 연결하여 다시 스택에 push합니다.

모든 문자를 처리하고 나면 스택의 최상단(top)에 최종 접미사 표기식이 남게 됩니다.

C++ 구현 코드

#include <iostream>
#include <stack>
using namespace std;

bool isOperator(char x) {
    switch (x) {
        case '+':
        case '-':
        case '/':
        case '*':
            return true;
    }
    return false;
}

string convertToPostfix(string prefix) {
    stack<string> expression;
    int length = prefix.size();
    
    // 뒤에서부터 역순으로 순회
    for (int i = length - 1; i >= 0; i--) {
        if (isOperator(prefix[i])) {
            string op1 = expression.top();
            expression.pop();
            string op2 = expression.top();
            expression.pop();
            string temp = op1 + op2 + prefix[i];
            expression.push(temp);
        }
        else
            expression.push(string(1, prefix[i]));
    }
    return expression.top();
}

int main() {
    string prefix = "*-AB/+CD*XY";
    cout<<"접두사 표기식 : "<<prefix<<endl;
    cout<<"접미사 표기식 : "<<convertToPostfix(prefix);
    return 0;
}

실행 결과

접두사 표기식 : *-AB/+CD*XY
접미사 표기식 : AB-CD+XY*/*

동작 원리 정리

위 코드의 동작 과정을 단계별로 살펴보면 다음과 같습니다.

문자열을 마지막 문자부터 첫 번째 문자까지 역순으로 탐색합니다.
탐색 중 만난 문자가 연산자(+, -, /, *)라면, 스택에서 두 개의 부분 표현식을 꺼내어 뒤에 연산자를 붙인 형태로 재구성합니다.
피연산자라면 그대로 문자열 형태로 스택에 쌓습니다.
역방향 순회 덕분에 연산자를 만나는 시점에는 이미 두 피연산자가 스택에 준비되어 있으므로, 별도의 중위 표기식 변환 없이 곧바로 접미사 형태로 조합할 수 있습니다.

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로, 입력 길이에 비례하여 선형적으로 동작하기 때문에 효율적입니다.