Prefix to Infix

Easy
0/40
Average time to solve is 10m
profile
Contributed by
43 upvotes
Asked in companies
SamsungInfo Edge India (Naukri.com)Hike

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)).
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
*-a/bc-/dkl


Expected Answer:
((a-(b/c))*((d/k)-l))


Output on console:
((a-(b/c))*((d/k)-l))


Explanation for Sample Input 1:
In this testcase, there are five operators ‘*’, ‘-’, ‘/’, ‘-’, ‘/’.
Prefix Expression: *-a/bc-/dkl.
The operator between  ‘b’ and ‘c’ is ‘/’. Resulting expression: *-a(b/c)-/dkl.
The operator between  ‘d’ and ‘k’ is ‘/’. Resulting expression: *-a(b/c)-(d/k)l.
The operator between  ‘a’ and ‘(b/c)’ is ‘-’. Resulting expression: *(a-(b/c))-(d/k)l.
The operator between  ‘d/k’ and ‘l’ is ‘-’. Resulting expression: *(a-(b/c))((d/k)-l).
The operator between  ‘(a-(b/c))’ and ‘((d/k)-l)’ is ‘*’. Resulting expression: ((a-(b/c))*((d/k)-l)).


Sample Input 2:
*-a/bc-/del


Expected Answer:
((a-(b/c))*((d/e)-l))


Output on console:
((a-(b/c))*((d/e)-l))


Expected Time Complexity:
Try to solve this in O(n^2), where n is the length of expression.


Constraints:
1 <= n <= 500
where n is the length of expression.

Time Limit: 1 sec
Hint

Can you find how to evaluate the expression? Which data structure can be used for the conversion?

Approaches (1)
Stack Based

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.
Time Complexity

O(|S|^2), where |S| is the length of the given string.

 

As we are iterating through the string once. We are performing push and pop operations on a stack both of which take constant time and concatenating the string which takes linear time.  Hence, the overall time complexity is O(|S|^2).

Space Complexity

O(|S|), where |S| is the length of the given string.

 

As we are storing the operator and operands in the stack. So, the maximum size of the stack can be |S|. Hence, the overall space complexity is O(|S|).

Code Solution
(100% EXP penalty)
Prefix to Infix
Full screen
Console