Be the first user to complete this post

  • 0
 Add to List
Medium

390. Convert Prefix to Postfix Expression

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

Example:

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

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

Approach: Use Stacks

Algorithm:

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

  1. If the character is operand, push it to the stack.
  2. If the character is operator,
    1. Pop an operand from the stack, say it's s1.
    2. Pop an operand from the stack, say it's s2.
    3. perform (s1 s2 operator) 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.

Output:

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

Related Problems: