C++로 후위 표기식(Postfix)을 중위 표기식(Infix)으로 변환하는 방법

문제 개요

이 문제에서는 후위 표기식(postfix)으로 작성된 수식이 주어지며, 우리의 과제는 이를 중위 표기식(infix) 형태로 변환하여 출력하는 것입니다.

중위 표기식(Infix expression)은 연산자가 피연산자 사이에 위치하는 표현식으로, 피연산자 연산자 피연산자 형태를 가집니다.

후위 표기식(Postfix expression)은 연산자가 피연산자 뒤에 오는 표현식으로, 피연산자 피연산자 연산자 형태를 가집니다.

후위 표기식은 컴퓨터 시스템이 계산하기에는 매우 효율적이지만, 사람이 직접 읽고 이해하기는 어렵습니다. 따라서 이러한 변환 과정이 필요합니다. 일반적으로 최종 사용자가 수식을 읽거나 수정할 때는 괄호로 구분되어 있어 이해하기 쉬운 중위 표기법이 사용됩니다.

예제를 통해 문제를 살펴보겠습니다.

입력 − xyz/*

출력 − (x * (y/z))

해결 접근 방법

이 문제는 스택(stack) 자료구조를 활용하여 해결할 수 있습니다. 후위 표기식을 한 글자씩 순회하면서 다음 두 가지 경우를 확인합니다.

경우 1 − 피연산자(operand)를 만나면 스택에 push합니다.

경우 2 − 연산자(operator)를 만나면 스택에서 피연산자 두 개를 pop한 뒤, 세 요소를 조합하여 중위 표기식을 만들고 이를 하나의 피연산자처럼 다시 스택에 push합니다.

순회가 모두 끝난 후 스택에 요소가 하나만 남아 있다면, 그 top 요소를 pop하면 그것이 바로 중위 표기식으로 변환된 결과입니다.

예제 코드

위에서 설명한 해결 방법을 구현한 C++ 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;
bool isOperand(char x) {
    return (x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z');
}
string infixConversion(string postfix) {
    stack<string> infix;
    for (int i=0; postfix[i]!='\0'; i++) {
        if (isOperand(postfix[i])) {
            string op(1, postfix[i]);
            infix.push(op);
        } else {
            string op1 = infix.top();
            infix.pop();
            string op2 = infix.top();
            infix.pop();
            infix.push("{"+op2+postfix[i]+op1 +"}");
        }
    }
    return infix.top();
}
int main() {
    string postfix = "xyae+/%";
    cout<<"The infix conversion of the postfix expression '"<<postfix<<"' is : ";
    cout<<infixConversion(postfix);
    return 0;
}

실행 결과

The infix conversion of the postfix expression 'xyae+/%' is : {x%{y/{a+e}}}