Home » Interview Questions » Stack Interview Questions » Postfix to Prefix Conversion

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.

Postfix to Prefix Conversion

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.

READ  Find Maximum Sum Possible Equal Sum of Three Stacks

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

References

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions