Prefix to Infix Conversion

In prefix to infix conversion problem, we have given expression in prefix notation. Write a program to convert it into an infix expression.

Prefix Notation

In this notation the operands are written after the operator. It is also known as Polish Notation.

For instance : +AB is an prefix expression.

Infix Notation

In this notation the operators are written between the operands. It is similar to how we generally write an expression.

For instance : A + B is an infix expression.

Example

Input : Prefix : *-A/BC-/ADE

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

Input : Prefix : *F/GH

Output : Infix : (F*(G/H))

Algorithm for Prefix to Infix Conversion

1. Initialize a string containing prefix expression.
2. Create a stack s of type string.
3. Traverse from the last character to first of the string and check if the current character is an operator pop the two top characters from the stack and concatenate them as a single string with a current operator in between. Push the string back into the stack.
4. Else if the current character is not an operator, push it as a string in the stack.
5. Return the top of the stack.

Implementation

C++ Program for Prefix to Infix Conversion

#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 Program for Prefix to Infix Conversion

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))

Complexity Analysis

Time Complexity: O(n) where n is the length of the prefix string.

Space Complexity: O(n) as we use space to store each of the n characters of the string.

References