Postfix to Prefix Conversion  

Difficulty Level Medium
Frequently asked in Amazon Factset Fanatics Oracle
Array Stack

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

Please click Like if you loved this article?

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.

Postfix to Prefix ConversionPin

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.

Please click Like if you loved this article?

See also
Backspace String Compare

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

References

Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.

Refresh