Convert Postfix to Infix in Java

In this article, we will continue with another problem related to application of Stack Data Structure. Given a Postfix Expression we have to convert into its Equivalent Infix Expression.

It is recommended to first learn Infix to postfix conversion before proceeding with this.

Now, let us have a quick recap. Infix Expressions are expressions where operators are written between every pair of operands and are of the form : x op y . Postfix Expressions are mathematical expressions where an operator is followed for every pair of operands and are of form : a b op . op is the operator, a and b are operands.

For Example: For the Postfix Expression: ABC-* , The Equivalent Infix will be A*(B - C).

Algorithm for Postfix to Infix in Java

  1. We traverse the given Postfix expression from left to right. We will use a single stack Infix which stores operands and at the end will hold our resultant Infix Expression.
  2. For each character, we will take two decisions:
    1. If the Character is a Operand we push it into Infix Stack.
    2. If the Character is a Operator, we pop two elements from the Stack, add last element with the operator and concatenate it with the first element and push the result back to the Infix Stack again for future evaluation.
  3. At the time of adding a part of evaluated expression we enclose them within Parentheses to determine the order of operations.
  4. When we traverse the whole string at the end, we will be left with only one value in our stack, which will be our Infix Expression.

Let us understand this with an example. Consider the Postfix expression : ABC- * D / .

Let us evaluate the given expression. We take decisions when we encounter Operator or Operands. The steps are:

  • Step 1: We start iterating through each character (ignoring the spaces). At i=0, char = ‘A’ an Operand. We push it into Infix stack. At i=1 and i=2 char = ‘B’ and ‘C’ respectively, we push them into Infix stack. The stack looks like:

  • Step 2: We continue, at i=3, char = ‘-‘ , an Operator we follow Step 2 Case 2, pop two elements from stack and add them with operator , we enclose the total expression within parentheses. Then, push the result back into stack. The stack now is :

    Now, (B-C) is an Operand .
  • Step 3: At i=4, we get char = ‘*’, an operator . So we repeat the above step and the Infix stack is now:

  • Step 4: At i=5, we get char = ‘D’ an operand we push it into stack.

  • Step 5: Finally at i=6, char =’/’, we perform Step 2 again by popping the two remaining elements and the Infix stack now is :

The Infix stack at last contains our resultant infix Expression which is : (( A * (B - C)) / D).

Implementation for Postfix to Infix in Java

Let us now look at the implementation of above in JAVA:

Output:

Let us look at the Time Complexity for this code. The time complexity is O(n), where n is the length of Postfix Expression.

So that’s all about Convert Postfix to Infix in Java. You can try out this code with different examples.


import_contacts

You may also like:

Related Posts

  • Prefix to postfix in java
    30 April

    Convert Prefix to Postfix in Java

    Learn about how to convert Prefix to Postfix in java.

  • Infix to Postfix Java
    24 April

    Infix to Postfix Conversion in Java

    Learn about how to convert infix to postfix expressions in java.

  • 23 September

    Sort a Stack using another stack

    Table of ContentsProblemSolution :Java codeComplete Java program to sort a stack using addition stack: If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions. In this post,  we will see how to sort a stack using another stack. Problem Given a Stack,  you need to sort it […]

  • 16 September

    Stack implementation in java

    Table of ContentsIntroductionStack basic operationsStack implementation using ArrayConclusion If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions. In this post, we will see how to implement Stack using Array in java. Introduction Stack is abstract data type which demonstrates Last in first out (LIFO) behavior. We […]

  • 15 September

    Check for balanced parentheses in an expression in java

    If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see how to check for balanced parentheses in an expression. Lets say, you have expression as a*(b+c)-(d*e) If you notice, above expression have balanced parentheses. Lets take another expression as (a*(b-c)*(d+e) If you observe, […]

  • 10 September

    Implement Stack using two Queues in java

    If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions. In this program, we will see how to implement stack using Linked List in java. Stack is abstract data type which demonstrates Last in first out (LIFO) behavior. We will implement same behavior using two queue. There […]

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.