이 문제에서는 전위 표기식(prefix expression)이 주어지며, 이를 중위 표기식(infix expression)으로 변환하여 출력하는 것이 목표입니다.
전위 표기식과 중위 표기식이란?
전위 표기식은 연산자가 피연산자 앞에 위치하는 표현식입니다.
예: +AB
중위 표기식은 연산자가 두 피연산자 사이에 위치하는 표현식으로, 우리가 일반적으로 수학에서 사용하는 방식입니다.
예: A+B
중위 표기식은 사람이 식을 이해하기 쉽도록 만들어진 형태입니다. 반면 컴퓨터는 실제 연산을 수행할 때 전위 또는 후위(postfix) 표기식(주로 후위 표기식)을 사용합니다.
문제 예시
입력: prefix : /+LM/NX 출력: infix : (L+M) / (N/X)
접근 방법: 스택(Stack) 활용
이 문제는 스택 자료구조를 이용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
1. 역순 순회: 전위 표기식을 뒤에서부터 앞으로(오른쪽 → 왼쪽) 탐색합니다.
2. 요소별 처리: 탐색 중 만나는 각 문자에 대해 아래 규칙을 적용합니다.
- 피연산자(operand)인 경우 → 해당 문자를 스택에 push 합니다.
- 연산자(operator)인 경우 → 스택에서 피연산자 2개를 pop 한 뒤, "피연산자 - 연산자 - 피연산자" 순서로 문자열을 조합하여 다시 스택에 push 합니다.
3. 결과 출력: 모든 문자를 탐색한 후, 스택의 최상단(top)에 남아 있는 문자열이 바로 중위 표기식으로 변환된 결과입니다. 이를 출력하면 됩니다.
C++ 구현 코드
#include <iostream>
#include <stack>
using namespace std;
bool isOperator(char element) {
switch (element) {
case '+':
case '-':
case '/':
case '*':
return true;
}
return false;
}
string convertToInfix(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 + prefix[i] + op2 + "}";
expression.push(temp);
} else {
expression.push(string(1, prefix[i]));
}
}
return expression.top();
}
int main() {
string prefix = "*-AB/+CD*XY";
cout << "Prefix expression : " << prefix << endl;
cout << "Infix expression : " << convertToInfix(prefix);
return 0;
}실행 결과
Prefix expression : *-AB/+CD*XY
Infix expression : {{A-B}*{{C+D}/{X*Y}}}동작 원리 상세 설명
위 코드에서 isOperator() 함수는 주어진 문자가 사칙연산자(+, -, /, *)인지 판별합니다.
convertToInfix() 함수는 문자열의 끝부터 시작하여 한 글자씩 확인합니다. 연산자를 만나면 스택에서 두 개의 피연산자(또는 부분식)를 꺼내 연산자를 가운데 두고 중괄호 {}로 묶어 하나의 문자열로 합친 뒤 다시 스택에 넣습니다. 이 과정을 반복하면 복잡한 중첩 구조의 중위 표기식이 완성됩니다.
복잡도 분석
- 시간 복잡도: O(n) — 표현식의 각 문자를 한 번씩만 순회합니다. 단, 문자열 결합이 빈번하게 발생하므로 실제 소요 시간은 문자열 길이에 영향을 받을 수 있습니다.
- 공간 복잡도: O(n) — 스택에 저장되는 부분식들을 위해 추가 공간이 필요합니다.