Infix Prefix Postfix Conversion (Stack)

February 23, 2023

Postfix Prefix Infix

Why we use Postfix Prefix & Infix?

Postfix, Prefix expressions are faster to execute for the compiler than simple infix expression, as the compiler doesnt have to care about operator predence in case of postfix and prefix.

Introduction

  • Operation : Any Expression of algebraic format (Example : A + B)
  • Operands : A and B or 5 & 6 are operands
  • Operators : +. -, %,*,/ etc are operators

Infix Notation

Infix is the day to day notation that we use of format A + B type. The general form can be classified as (a op b) where a and b are operands(variables) and op is Operator.

  • Example 1 : A + B
  • Example 2 : A * B + C / D

Postfix Notation

Postfix is notation that compiler uses/converts to while reading left to right and is of format AB+ type. The general form can be classified as (ab op) where a and b are operands(variables) and op is Operator.

  • Example 1 : AB+
  • Example 2 : AB*CD/+

Prefix Notation

Prefix is notation that compiler uses/converts to while reading right to left (some compilers can also read prefix left to right) and is of format +AB type. The general form can be classified as (op ab) where a and b are operands(variables) and op is Operator.

  • Example 1 : +AB
  • Example 2 : +*AB/CD
Infix postfix prefix conversion(stack)

Why Postfix/Prefix Expressions are faster than Infix?

For Infix Expression which is format A+B*C, if the compiler is reading left to right then it can’t evaluate A+B first until it has read whole expression and knows expression is actually A + (B*C) i.e. B * C needs to be implemented first

Postfix for above infix is ABC*+. Now, as soon as compiler sees two operands followed by operator it can implement it without caring for precedence.

  • Assume ABC*+
  • ABC*+ (BC* is implemented as B*C and result is put back)
  • AX+ (Assuming X stores result of BC* i.e. B*C)
  • Now finally AX+ can be implemented as A+X
DSA desktop gif
DSA mobile gif

Representation of a Stack as an Array

Representation of a Stack as a Linked List

Infix to Postfix Conversion

Infix to prefix conversion

Postfix to Prefix Conversion

Problem (This is how to convert manually for MCQ Question in the exam)

Problem

  • Infix: a + b * c + d can be written as a + (b * c) + d
  • Now, for all + – / * associativity is left to right we will write it as
  • (a + (b * c)) + d and thus further ((a + (b * c)) + d)
  • Solving and converting innermost bracket to postfix
  • Step 1 –((a + bc*)+ d)
  • Step 2 – Consider bc* as separate operand x the innermost bracket now looks like ((a + x)+ d)
    • Applying postfix it looks like – (ax+ + d)replacing x here (abc*+ + d)
  • Step 3 – Consideringabc*+as separate operand z, the final bracket looks like – (z + d)the result would be zd+
    • replacing z value = abc*+d+

Algorithm (For Code/Manual Calculation)

  1. First Start scanning the expression from left to right
  2. If the scanned character is an operand, output it, i.e. print it
  3. Else
    • If the precedence of the scanned operator is higher than the precedence of the operator in the stack(or stack is empty or has'(‘), then push operator in the stack
    • Else, Pop all the operators, that have greater or equal precedence than the scanned operator. Once you pop them push this scanned operator. (If we see a parenthesis while popping then stop and push scanned operator in the stack)
  4. If the scanned character is an ‘(‘, push it to the stack.
  5. If the scanned character is an ‘)’, pop the stack and output it until a ‘(‘ is encountered, and discard both the parenthesis.
  6. Now, we should repeat the steps 2 – 6 until the whole infix i.e. whole characters are scanned.
  7. Print output
  8. Do the pop and output (print) until stack is not empty
Infix to Postfix Conversion in C++

Infix to Prefix

Problem (This is how to convert manually for MCQ Question in the exam)

  • Infix: (a / b + c) - ( d + e * f) can be written as ((a / b) + c) - ( d + (e * f))
  • Now, we have done the above according to associativity
  • Solving and converting innermost bracket to prefix
  • Step 1 –(/ab + c) - ( d + *ef)
  • Step 2 – Consider /ab and *ef as separate operand x and y
  • the innermost bracket now looks like (x + c) - (d + y)
    • Applying prefix it looks like – (+xc - +dy)replacing x and y here (+/abc - +d*ef)
  • Step 3 – Considering+/abc and+d*efas separate operand z and w, the final bracket looks like – (z - w)the result would be -zw
    • replacing z and w value = -+/abc+d*ef

Algorithm (For Code/Manual Calculation)

Given Infix - ((a/b)+c)-(d+(e*f))
  • Step 1: Reverse the infix string. Note that while reversing the string you must interchange left and right parentheses.
  • Step 2: Obtain the postfix expression of the expression obtained from Step 1.
  • Step 3: Reverse the postfix expression to get the prefix expression

This is how you convert manually for theory question in the exam

    1. String after reversal – ))f*e(+d(-)c+)b/a((
    2. String after interchanging right and left parenthesis – ((f*e)+d)-(c+(b/a))
    3. Apply postfix – Below is postfix (On this page you check infix to postfix conversion rule)
    4. Reverse Postfix Expression (Given After the image below)
Sr. No. Expression Stack Prefix
0 ( (
1 ( ((
2 f (( f
3 * ((* f
4 e ((* fe
5 ) ( fe*
6 + (+ fe*
7 d (+ fe*d
8 ) fe*d+
9 – – fe*d+
10 ( -( fe*d+
11 c -( fe*d+c
12 + -(+ fe*d+c
13 ( -(+( fe*d+c
14 b -(+( fe*d+cb
15 / -(+(/ fe*d+cb
16 a -(+(/ fe*d+cba
17 ) -(+ fe*d+cba/
18 ) – fe*d+cba/+
19 fe*d+cba/+- 
Final prefix: -+/abc+d*ef

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