Convert Prefix to Postfix in Java

Prefix to postfix in java

In this article we continue with another interesting problem related to Stack data structure. Given a Prefix expression, convert into its Equivalent Postfix Expression.

It is recommended to first go through Infix to postfix conversion for better understanding.

Let us understand what we mean by Prefix and Postfix Expression.

Prefix Expression is an expression where operators precede the operands. In simpler terms, the operators appear before the operands in the expression. They are of form : op X Y, op is operator and X,Y are operands. For Example: +AB is a Prefix Expression for Infix: A+B.

Postfix Expressions re of the form X Y op, where operators come after operands. For Example: AB+ is the Postfix for Infix: A+B.

We need to convert Prefix to Postfix so for the Prefix Expression : + / AB * CD , the Infix will be : (A / B) + (C * D). Then on converting this infix the resultant Postfix Expression will be : AB/ CD* + .

Now, to convert Prefix expression into Postfix, we can try first converting the Prefix into Infix notation then convert the result into Postfix. But, we can do this in a single step by directly converting the Prefix into Postfix. Let us look at the Algorithm.

Algorithm for prefix to postfix

  1. We will start traversing the Prefix Expression from Right to Left, unlike what we did in Infix to Postfix Conversion. We will use a single Stack Postfix which will hold the operands and a part of evaluated Postfix expression. When we reach the end ( at i = -1) , the stack will hold the resultant Postfix expression.
  2. For each character we encounter, we consider two cases:
    1. f the Character is a Operand we push it into the Postfix Stack.
    2. If the Character is a Operator we pop two elements from the Stack, add two elements together followed with the operator and push the result back to the Postfix Stack again for future evaluation. This will be the part of total Postfix.
  3. When we come to end of the String traversing from Right (Length-1) to Left (0) , at i=-1 we stop and at the at the end the Postfix stack contain only one value, which will be the resultant Postfix Expression.

Now, let us understand this algorithm with an example. Consider the Prefix expression : /+AB-CD. The Infix for this is : ((A + B) / (C – D)).

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

  • Step 1: We start iterating from the end of the string (length – 1 = 7 – 1 = 6 ) to start index. At i=6, we have char = ‘D’, an operand so we push it into the Postfix Stack. At i=5, we have char = ‘C’, we push it into the stack. The Postfix stack now is:

  • Step 2: We continue iteration at i=4, char = ‘-‘ , an operator, so we pop two operands from stack and add them with the operator in the same order. We then push the result (CD-) into the Postfix stack again for future evaluation. The stack now is:

    Now, CD- is an Operand.
  • Step 3: Now at i=3, we have char = ‘B’, and at i=2, we have char = ‘A’, since both are operands so we push them into stack one by one . The Postfix stack is now:

  • Step 4: At i=1, char = ‘+’, an Operator. So we perform Step 2 again by popping and adding the two elements with the operator and then push the result (AB+) back to stack. The Postfix stack now looks :

  • Step 5: Finally At i=0, we get char =’/’, an Operator so we pop both the operands (AB+ and CD-) and add it with the operator. We stop iteration as we reached index 0. The Postfix stack at the end now contains our resultant Postfix Expression which is :

    The Postfix is: AB+ CD- /

Implementation for Prefix to postfix conversion in java

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

Output:

We have implemented two examples. Now let us look at the Time Complexity of our approach.

Time complexity

Time Complexity: As we traverse the whole input string once and the stack operations require constant time, the overall time complexity is O(n), n is the length of Prefix Expression.

So that’s all about how to convert Prefix to postfix in java. You can try with different examples and execute this code for better understanding.


import_contacts

You may also like:

Related Posts

  • 30 April

    Convert Postfix to Infix in Java

    Learn about how to convert Postfix to Infix 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.