이 문제에서는 접두어 표현식이 제공됩니다. 우리의 임무는 주어진 표현식의 중위 변환을 출력하는 것입니다.
접두사 표현식은 피연산자 앞에 연산자가 있는 표현식입니다.
예:+AB.
중위 표현식은 피연산자 사이에 연산자가 있는 표현식입니다.
예:A+B
중위 표현은 인간이 이해할 수 있는 정보이지만 컴퓨터는 접두사 또는 접미사 식(일반적으로 접미사)에 대해 계산을 수행합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
Input: prefix : /+LM/NX Output: infix : (L+M) / (N/X)
이 문제를 해결하기 위해 스택 데이터 구조를 사용할 것입니다. 표현식의 역순으로 접두어 표현식을 탐색합니다. 그리고 표현식의 각 요소에 대해 이러한 경우를 확인합니다.
요소가 피연산자인 경우 -> 스택의 푸시(요소)
element가 operator -> 2Xpop(topofstack)인 경우 string =operand - operator - operand로 순서대로 푸시합니다.
마지막으로 순회 후에 스택의 맨 위에는 중위 변환인 문자열이 포함되어 인쇄합니다.
솔루션 구현을 보여주는 프로그램
예
#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}}}