Convert Prefix to Infix Expression

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

Example:

Input: Prefix expression: + A B
Output: Infix expression- (A + B)

Input: Prefix expression: *-A/BC-/AKL
Output: Infix expression: ((A-(B/C))*((A/K)-L))

Approach: Use Stacks

Algorithm:

Iterate the given expression from right to left (in reverse order), one character at a time

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

Please walk through the example below for more understanding.

Java Code:

Output:

Prefix Expression: *-A/BC-/AKL
Infix Expression: ((A-(B/C))*((A/K)-L))

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

%d bloggers like this: