접두사에서 중위로 변환

접두사에서 중위로 변환 문제에서 접두사 표기법으로 표현했습니다. 중위 식으로 변환하는 프로그램을 작성하십시오.

접두사 표기법

이 표기법에서 피연산자는 연산자 뒤에 기록됩니다. 폴란드어 표기법이라고도합니다.

예 : + AB는 접두사 식입니다.

중위 표기법

이 표기법에서 연산자는 피연산자 사이에 기록됩니다. 일반적으로 표현을 쓰는 것과 비슷합니다.

예를 들어 : A + B는 중위 식입니다.

핀

예

입력 : 접두사 : * -A / BC- / ADE

출력 : 중위 : ((A- (B / C)) * ((A / D) -E))

입력 : 접두사 : * F / GH

출력 : 중위 : (F * (G / H))

접두사에서 중위로 변환하는 알고리즘

1. 초기화 현 접두사 표현을 포함합니다.
2. 문자열 유형의 스택을 만듭니다.
3. 마지막 문자에서 문자열의 첫 번째 문자로 이동하고 현재 문자가 연산자인지 확인합니다. 스택에서 두 개의 최상위 문자를 팝하고 그 사이에 현재 연산자가있는 단일 문자열로 연결합니다. 문자열을 다시 스택.
4. 그렇지 않으면 현재 문자가 연산자가 아니면 스택의 문자열로 푸시합니다.
5. 스택의 맨 위를 반환합니다.

실시

접두사에서 중위로 변환하기위한 C ++ 프로그램

#include <iostream> 
#include <stack> 
using namespace std; 
  
bool isOperator(char x){ 
    switch(x){ 
      case '+': 
      case '-': 
      case '/': 
      case '*': 
        return true; 
    } 
  return false; 
} 
  
string prefixToInfix(string prefix_exp) { 
  stack<string> s; 
  
  int l = prefix_exp.size(); 
  
  for(int i = l-1; i >= 0; i--){ 
  
    if(isOperator(prefix_exp[i])){ 
  
      string op1 = s.top();   
      s.pop(); 
      string op2 = s.top();   
      s.pop(); 
  
      string temp = "(" + op1 + prefix_exp[i] + op2 + ")"; 
  
      s.push(temp); 
    } 
  
    else{ 
      s.push(string(1, prefix_exp[i])); 
    } 
  } 
  
  return s.top(); 
} 
  
int main(){ 
  string prefix_exp = "*-A/BC-/ADE"; 

  cout<<"Infix : "<<prefixToInfix(prefix_exp); 
  
  return 0; 
}

Infix : ((A-(B/C))*((A/D)-E))

접두사에서 중위로 변환을위한 Java 프로그램

import java.util.*;

class Prefix{
    
    static boolean isOperator(char x){ 
        switch(x){ 
          case '+': 
          case '-': 
          case '/': 
          case '*': 
            return true; 
        } 
      return false; 
    } 
      
    static String prefixToInfix(String prefix_exp) { 
      Stack<String> s= new Stack<String>();
      
      int l = prefix_exp.length(); 
      
      for(int i = l-1; i >= 0; i--){ 
      
        if(isOperator(prefix_exp.charAt(i))){ 
      
          String op1 = s.peek();   
          s.pop(); 
          String op2 = s.peek();   
          s.pop(); 
      
          String temp = "(" + op1 + prefix_exp.charAt(i) + op2 + ")"; 
      
          s.push(temp); 
        } 
      
        else{ 
          s.push(prefix_exp.charAt(i)+""); 
        } 
      } 
      
      return s.peek(); 
    } 
      
    public static void main (String[] args){
        
    String prefix_exp = "*-A/BC-/ADE"; 
    System.out.println("Infix : "+prefixToInfix(prefix_exp));
    
  }
}

Infix : ((A-(B/C))*((A/D)-E))

복잡성 분석

시간 복잡성 : O (n) 여기서 n은 접두사 문자열의 길이입니다.

공간 복잡성 : 공백을 사용하여 문자열의 n 개 문자를 각각 저장하므로 O (n).

참조