- Prepare
All Platforms Programming Aptitude Syllabus Interview Preparation Interview Exp. Off Campus - Prime Video
- Prime Mock

- Interview Experience
- Prime VideoNew
- Prime Mock
- Interview Prep
- Nano Degree
- Prime Video
- Prime Mock

# Infix Prefix Postfix Conversion (Stack)

## Why we use Postfix Prefix & Infix?

**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

*and*

**a***are operands(variables) and*

**b***is Operator.*

**op**- 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

*where*

**(ab op)***and*

**a***are operands(variables) and*

**b***is Operator.*

**op**- 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

*where*

**(op ab)***and*

**a***are operands(variables) and*

**b***is Operator.*

**op**- Example 1 : +AB
- Example 2 : +*AB/CD

## 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

Compiler converts infix expression to postfix/prefix at compile time, so at runtime your calculations are always happening in post-prefix. A website's code maybe compiled once a week but it may need to run 1 million times a week.

Which is why we prefer that runtime execution should be as fast as possible. If calculations happen faster than we have optimized our page load time hugely right?

### 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)`

- Applying postfix it looks like –
- Step 3 – Considering
`abc*+`

as separate operand z, the final bracket looks like –`(z + d)`

the result would be`zd+`

- replacing z value =
`abc*+d+`

- replacing z value =

#### Alert

The above may give wrong results sometimes, which is why its always safer to use below algorithm for both coding and manual calculation -Also note below algorithm is given wrong on Geeks4Geek website, only refer from here.(As most codes are made by interns and PrepInsta pages are made by Ph.D Teachers)

### Algorithm (For Code/Manual Calculation)

- First Start scanning the expression from left to right
- If the scanned character is an operand, output it, i.e. print it
- 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)

- If the scanned character is an ‘(‘, push it to the stack.
- If the scanned character is an ‘)’, pop the stack and output it until a ‘(‘ is encountered, and discard both the parenthesis.
- Now, we should repeat the steps 2 – 6 until the whole infix i.e. whole characters are scanned.
- Print output
- Do the pop and output (print) until stack is not empty

## 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)`

- Applying prefix it looks like –
- Step 3 – Considering
`+/abc`

and`+d*ef`

`as 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`

- replacing z and w value =

#### Alert

The above may give wrong results sometimes, which is why its always safer to use below algorithm for both coding and manual calculation -Also note below algorithm is given wrong on Geeks4Geek website, only refer from here.(As most codes are made by interns and PrepInsta pages are made by Ph.D Teachers)

### 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

**String after reversal –**))f*e(+d(-)c+)b/a((**String after interchanging right and left parenthesis**– ((f*e)+d)-(c+(b/a))**Apply postfix –**Below is postfix (On this page you check infix to postfix conversion rule)**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

### Stacks

- Introduction to Stack in Data Structure
- Operations on a Stack
- Stack: Infix, Prefix and Postfix conversions
- 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)
- Queues Program in C and implementation
- Implementation of Queues using Arrays | C Program
- Types of Queues in Data Structure
- Application of Queue Data Structure
- 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

- Circular queue in Data Structure
- Applications of Circular Queues
- Circular queue in – C | C++ | Java
- Circular queue using Array – C | C++ | Java
- Circular Queue using Linked Lists – C | C++ | Java

### Priority Queue

### 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

- Circular queue in Data Structure

Click Here - Applications of Circular Queues

Click Here - Circular queue in –

C | C++ | Java - Circular queue using Array –

C | C++ | Java - Circular Queue using Linked Lists –

C | C++ | Java

Login/Signup to comment