C++의 접미사에서 중위사로

이 문제에서는 접미사 형식의 표현식이 주어지며 우리의 임무는 표현식의 중위어 형식을 인쇄하는 것입니다.

중위 표현 피연산자 연산자 피연산자와 같이 연산자가 피연산자의 중간에 있는 표현식입니다.

접미사 표현식 피연산자 연산자와 같이 연산자가 피연산자 뒤에 오는 표현식입니다.

후위 표현식은 시스템에서 쉽게 계산할 수 있지만 사람이 읽을 수는 없습니다. 따라서 이 변환이 필요합니다. 일반적으로 최종 사용자의 읽기 및 편집은 괄호로 구분되어 사람이 쉽게 이해할 수 있는 중위 표기법으로 수행됩니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 - xyz/*

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

이 문제를 해결하기 위해 스택 데이터 구조를 사용합니다. 그리고 접미사 식을 하나씩 순회하고 다음 경우를 확인하십시오 -

사례 1 - 피연산자가 발견되면 스택에 푸시합니다.

사례 2 - 연산자가 발견되면 피연산자를 팝하고 3개의 중위 표현식을 만들고 표현식을 피연산자로 푸시합니다.

스택에 하나의 요소만 남아 있고 순회가 완료되면 스택의 맨 위를 팝하는 것이 중위 변환입니다.

예시

솔루션 구현을 보여주는 프로그램입니다.

#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}}}