Last Updated: 4 Mar, 2021

Prefix to Infix

Easy

Asked in companies

Solve now

Problem statement

You are given a string denoting a valid Prefix expression containing ‘+’, ’-’, ’*’, ‘/’ and lowercase letters.

Convert the given Prefix expression into an Infix expression.

Note:

Infix notation is a method of writing mathematical expressions in which operators are placed between operands. For example, "a + b" represents the addition of a and b.

Prefix notation is a method of writing mathematical expressions in which operators are placed before the operands. For example, "+ a b" represents the addition of a and b.

Expression contains lowercase English letters, ‘+’, ‘-’, ‘*’, and  ‘/’.

Example:

Input: /-ab+-cde

Output: ((a-b)/((c-d)+e))

Explanation:
In this test case, there are four operators ‘/’, ‘-’, ‘+’, ‘-’.
Prefix expression:  /-ab+-cde. 
The operator between  ‘a’ and ‘b’ is ‘-’. Resulting expression: /(a-b)+-cde.
The operator between  ‘c’ and ‘d’ is ‘-’. Resulting expression: /(a-b)+(c-d)e.
The operator between ‘c-d’ and ‘e’ is +. Resulting expression: /(a-b)((c-d)+e).
The operator between ‘a-b’ and ‘((c-d)+e)’ is ‘/’. Resulting expression: ((a-b)/((c-d)+e)).

Input Format:

The first line of input contains a string, denoting the given prefix expression.

Output Format:

Return the infix expression corresponding to the given prefix expression.

Note:

You don’t need to print anything. You just need to implement the given function.

Solve now

Approaches

01 Approach

The idea is to iterate over the expression from right to left and store the operands in a stack. Here, we are using a stack of strings for storing the operands. Whenever we encounter an operator, pop the top two operands from the stack and convert the expression to its infix form and then push back to the stack.

Iterate from ‘i’ = |S| - 1 to 0. The idea behind this step is to store the operands.
1. If the current character is an operand, push it onto the stack.
2. If the current character is an operator, pop two operands/ expressions from the stack let’s say the two elements popped from the stack are ‘OPERAND1’ and ‘OPERAND2’, create a string ( OPERAND1 + S[i] + OPERAND2 ), and then push this string into the stack.
The element at the top of the stack will be the final infix expression.

Solve now