Infix to Postfix
Any operation can be expressed in Infix, postfix and prefix, we shall see how to convert infix to prefix operation via manual calculation and via code. Lets have a look at Infix to postfix conversion using stack in C
Infix to Postfix in C
- Infix – Any operation of format
a op bformat examplea + bis called an infix operation - Postfix – An operation or expression can also be written in the format of
a b opi.e.a b +which is similar to writinga + bin infix. All we are doing is shifting operator to the right of operands
Why we need postfix operator?
For a compiler, it is easier to read postfix or prefix operation. As a compiler either reads from right to left or left to right. Let us understand this with the help of an example –
Imagine the following - a + b * c + d
- Let us assume compiler starts reading from right to left
- It reads
c + dthe operation first and it would be efficient if it could’ve implemented it, but, it can’t as next operation isc * bwhich has higher precedence and must be implemented first. - Thus, if the compiler reads a notation in which, it can keep on implementing operations as soon as it sees them right!
The corresponding Postfix would be: abc*+d+
Steps to convert
- Any infix
op1 oper op2can be written asop1 op2 oper- Where op1 = Operand 1
- op2 = Operand2
- oper = Operation
- Example
a + bcan be written asab+in postfix
Problem
- Infix:
a + b * c + dcan be written asa + (b * c) + d - Now, for all + – / * associativity is left to right we will write it as
(a + (b * c)) + dand thus further((a + (b * c)) + d)- Solving and converting innermost bracket to postfix
- Step 1 –
((a + bc*)+ d) - Step 2 – Consider
bc*as separate operandxthe 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 bezd+- replacing z value =
abc*+d+
- replacing z value =
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)Alert
The above may give wrong results sometimes, which is why its always safer to use below algorithm for both coding and manual calculation -
Algorithm
- 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
Representation of a Stack as an Linked List
Representation of a Stack as an Array
Infix to prefix conversion
Postfix to Prefix Conversion
Queues In Data Structures
Program for Infix to Postfix in C
We will discuss two methods –
- Method 1: Using array-based stack approach
- Method 2: Using struct based stack approach
Method 1
Method 2
Method 1
Method 2
Output
abc*+d-
Handling all the cases
In the above program, we assumed that expression will only contain alphabets as operands and ‘(‘ or ‘)’ as brackets.
The below program will handle the cases
- Operands: alphabets or digits
- Example – a-z or A-Z or 0 – 9
- Brackets: { } or [ ] or ( )
Code for this Program
Method 1
Method 2
Method 1
Method 2
Output
a35*d-
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
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
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
- 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
- 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
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
