Postfix to Prefix Conversion

In this problem, we have given a string that denotes the postfix expression. We have to do postfix to prefix conversion.

Prefix Notation

In this notation, we write the operands after the operator. It is also known as Polish Notation.

For instance: +AB is a prefix expression.

Postfix Notation

In this notation, we write the operands before the operator. It is also known as Reverse Polish Notation. For instance: AB+ is a postfix expression. Given an expression in postfix notation. Write a program to convert the given notation in prefix notation.

Example

Input : Postfix : ABC/-AD/E-*

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

Input : Postfix : AB+CD-*

Output : Prefix : *+AB-CD

Algorithm for Postfix to Prefix Conversion

1. Initialize a string containing postfix expression.
2. Create a stack s of type string.
3. Traverse from the start to end of the string and check if the current character is an operator pop the two top characters from the stack and concatenate them as CURRENT OPERATOR + SECOND CHARACTER + FIRST CHARACTER. 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 Postfix to Prefix Conversion

#include <bits/stdc++.h> 
using namespace std; 
  
bool isOperator(char x){ 
    switch (x){ 
        case '+': 
        case '-': 
        case '/': 
        case '*': 
            return true; 
        } 
    return false; 
} 
  
string postfixToPrefix(string postfix_exp){ 
    stack<string> s; 
  
    int l = postfix_exp.size(); 
  
    for(int i = 0; i<l; i++){ 
  
        if (isOperator(postfix_exp[i])){ 
  
            string op1 = s.top(); 
            s.pop(); 
            string op2 = s.top(); 
            s.pop(); 
  
            string temp = postfix_exp[i] + op2 + op1; 
  
            s.push(temp); 
        } 
  
        else{ 
            s.push(string(1, postfix_exp[i])); 
        } 
    } 
  
    return s.top(); 
} 
  
int main(){
    
    string postfix_exp = "ABC/-AD/E-*"; 
    cout<<"Prefix : "<<postfixToPrefix(postfix_exp); 
    
    return 0; 
}

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

Java Program for Postfix to Prefix Conversion

import java.util.*; 
  
class Postfix{ 
  
    static boolean isOperator(char x){ 
  
        switch (x){ 
            case '+': 
            case '-': 
            case '/': 
            case '*': 
                return true; 
        } 
        return false; 
    } 
  
    static String postfixToPrefix(String postfix_exp){ 
        Stack<String> s = new Stack<String>(); 
  
        int l = postfix_exp.length(); 
  
        for(int i = 0; i<l; i++){ 
  
            if(isOperator(postfix_exp.charAt(i))){ 
  
                String op1 = s.peek(); 
                s.pop(); 
                String op2 = s.peek(); 
                s.pop(); 
  
                String temp = postfix_exp.charAt(i) + op2 + op1; 
  
                s.push(temp); 
            } 
  
            else{ 
                s.push(postfix_exp.charAt(i) + ""); 
            } 
        } 
  
        return s.peek(); 
    } 
  
    public static void main(String args[]){
        
        String postfix_exp = "ABC/-AD/E-*"; 
        System.out.println("Prefix : " + postfixToPrefix(postfix_exp));
        
    } 
}

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

Complexity Analysis

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

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

References