Convert Postfix to Prefix Expression

Objective: Given a Postfix expression, write an algorithm to convert it into prefix expression.

Example:

Input: Postfix expression:  A B + 
Output: Prefix expression- + A B

Input: Postfix expression:  ABC/-AK/L-*
Output: Infix expression: *-A/BC-/AKL

Approach: Use Stack

Algorithm:

Iterate the given expression from left to right, one character at a time

  1. If the character is operand, push it to stack.
  2. If the character is operator,
    1. Pop operand from the stack, say it’s s1.
    2. Pop operand from the stack, say it’s s2.
    3. perform (operator s2 s1) and push it to stack.
  3. Once the expression iteration is completed, initialize the result string and pop out from the stack and add it to the result.
  4. Return the result.

Please walk through the example below for more understanding.

Java Code:

Output:

Postfix Expression: ABC/-AK/L-*
Prefix Expression: *-A/BC-/AKL

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: