Postfix to Prefix Conversion Program using Stack in C++

February 23, 2023

Postfix to Prefix Conversion in C++

 

Prefix, Postfix and Infix are the different ways to write expressions as notations. In infix, they are normal notations as used by mathematical expressions in copies. In Prefix expression, the  operator is prefixed to operands, and in Postfix, or Reverse Polish Notation, the operator comes after the operands. In this article we will know how to perform Post fix expressions to prefix expressions converstion using a stack in C++.

Postfix to prefix expression

What is Postfix to Prefix?

Infix: (X + Y)

  • Postfix – The postfix will look like, XY+
  • Prefix: The prefix will look like, +YX

Infix : (X + Y) / (U – V)

  • Postfix – The postfix will look like, XY+UV-/
  • Prefix – The prefix will look like, /+XY-UV

Here we need to use a stack data structure. SInce we have our own inbuilt stack DS in C++ STL, we are going to use it. If you use want to know more about that : Stack in C++ STL 

Follow this algorithm to solve this problem.

There may be  many ways to find the post fix to prefix, here it goes one easy way to imlement an algorithm to do so.

  • Read the expression from left to right.
  • If there is any operand present, push it to a stack.
  • Then if you come accross an operator, pop two of the opearands from the stack and concatinate them like,
    the operator + 2nd top value of the stack + first top value of the stack.
  • Repeat the process.
  • Reverse the string at the end.

Fun fact: This can be interpreted as a binary tree if you can make a binary tree with operators and add the operands at last.
DSA desktop gif
DSA mobile gif

Stack Representation in C++

Representation of a Stack as an Array

Representation of a Stack as a Linked List

Infix to postfix conversion

Infix to prefix expression

Visual Implementation of the Algorithm :

Suppose the expression in Infix is (X+Y)/(U-V), and in Postfix: XY+UV-/ 

Here all the iterations are shown below.

Postfix to prefix conversion-2
Postfix to prefix conversion – 1

The code to implement this:

Run 
#include<bits/stdc++.h>
using namespace std;
int IsOperator(char x)
{
   switch (x) {
      case '+':
      case '-':
      case '/':
      case '*':
                 return 1;
   }
   return 0;
}

int main()
{
    string s,c="";
    cout<<"Enter the Postfix Expression: "<>s;
    stack st;
    cout<<"The Prefix expression is: "<=0;i--)
    {
         if(IsOperator(s[i]))
            st.push(s[i]);
         else{
              c+=s[i];
             while(!st.empty() && st.top()=='#')
            {
                st.pop();
                c+=st.top();             
                st.pop();
            }
     st.push('#');
    }
  }
    reverse(c.begin(),c.end());
   cout<

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout

Stacks

  • Introduction to Stack in Data Structure
    Click Here
  • Operations on a Stack
    Click Here
  • Stack: Infix, Prefix and Postfix conversions
    Click Here
  • Stack Representation in –
    C | C++ | Java
  • Representation of a Stack as an Array. –
    C | C++ | Java
  • Representation of a Stack as a Linked List. –
    C | C++ | Java
  • Infix to Postfix Conversion –
    C | C++ | Java
  • Infix to prefix conversion in –
    C | C++ | Java
  • Postfix to Prefix Conversion in –
    C | C++ | Java

Queues

  • Queues in Data Structures (Introduction)
    Click Here
  • Queues Program in C and implementation
    Click Here
  • Implementation of Queues using Arrays | C Program
    Click Here
  • Types of Queues in Data Structure
    Click Here
  • Application of Queue Data Structure
    Click Here
  • Insertion in Queues Program (Enqueuing) –
    C | C++ | Java
  • Deletion (Removal) in Queues Program(Dequeuing) –
    C | C++ | Java
  • Reverse a Queue –
    C | C++ | Java
  • Queues using Linked Lists –
    C | C++ | Java
  • Implement Queue using Stack –
    C | C++ | Java
  • Implement Queue using two Stacks –
    C | C++ | Java

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction –
    C | C++ | Java
  • Priority Queue Implementation using Array –
    C | C++ | Java
  • Priority Queue using Linked List –
    C | C++ | Java
  • Priority Queue Insertion and Deletion-
    C | C++ | Java

Stacks

Queues

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction – C | C++ | Java
  • Priority Queue Implementation using Array – C | C++ | Java
  • Priority Queue using Linked List – C | C++ | Java
  • Priority Queue Insertion and Deletion- C | C++ | Java