이 문제에서는 접두어 표현식이 제공됩니다. 우리의 임무는 주어진 표현식의 후위 변환을 출력하는 것입니다.
접두사 표현식은 피연산자 앞에 연산자가 있는 표현식입니다.
예:+AB.
접미사 표현식은 표현식에서 피연산자 뒤에 연산자가 있는 표현식입니다.
예:AB/
접두어를 접미사로 변환할 때 중위로 변환하면 안 됩니다.
문제를 이해하기 위해 예를 들어보겠습니다.
Input: /+XY+NM Output: XY+NM+/ Explanation: infix -> (X+Y)/(N+M)
이 문제를 해결하기 위해 먼저 전체 후위 표현식을 역순으로 탐색합니다. 그리고 처리를 위해 스택 데이터 구조를 사용할 것입니다. 그리고 순회에서 발견된 요소의 경우 다음을 수행하십시오.
사례:기호가 피연산자인 경우 -> 스택의 푸시(요소)
사례:기호가 연산자인 경우 -> 스택에서 2*pop(요소). 그런 다음 피연산자 - 피연산자 - 연산자의 시퀀스를 푸시합니다.
알고리즘 구현을 보여주는 프로그램
예시
#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 expression : "<<prefix<<endl;
cout<<"Postfix expression : "<<convertToPostfix(prefix);
return 0;
} 출력
Prefix expression : *-AB/+CD*XY Postfix expression : AB-CD+XY*/*