PostFix To Prefix

Easy
0/40
Average time to solve is 20m
profile
Contributed by
20 upvotes
Asked in companies
SAP LabsShareChat

Problem statement

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


Convert the given Postfix expression into a Prefix expression.


Note: 
Postfix notation is a method of writing mathematical expressions in which operators are placed after the 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: abc*+

Output: +a*bc

Explanation:
For the given postfix expression, infix expression is a+b*c. And it's corresponding prefix expression is +a*bc.


Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a string ‘s' which denotes the Postfix expression.


Output Format: 
Return a string which denotes the corresponding prefix expression.


Note: 
You do not need to print anything, and it has already been taken care of. Just implement the given function.
Sample Input 1:
ab+cd-*


Expected Answer:
*+ab-cd


Output on console:
*+ab-cd


Explanation Of Sample Input 1:
For this testcase, the infix expression will be (a + b) * (c - d). Hence, our prefix expression will be *+ab-cd.


Sample Input 2:
ab+c-


Expected Answer:
-+abc


Output on console:
-+abc


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


Constraints:
1 <= |s| <= 10^5

Time Limit: 1 sec
Hint

Can stack help to solve this problem?

Approaches (1)
Greedy Approach

Here, to convert from postfix to prefix, we can simply use stack data structure. We will be following two conditions as follow:

  • If we encounter an operand, then we will push it into the stack
  • If we encounter an operator, then we can pop 2 elements from the stack, create a new string in prefix format and push it back to the stack

This process should repeat till the end of prefix expression.

 

Algorithm:

 

  • Declare a stack ‘stk’ of string type.
  • Run a loop from ‘i’ = ‘0’ to the length of the postfix string
    • If we encounter an operator, then we can pop 2 elements from the stack, create a new string in prefix format and push it back to the stack.
    • Else, if we encounter an operand, then we will push it into the stack.
  • Iterate over the stack and concatenate all the strings and return the answer.
Time Complexity

O(N) where ‘N’ is the length of the string.

 

Here, we are iterating over the entire Postfix expression which requires ‘N’ iterations. Hence, our time complexity is O(N).

Space Complexity

O(N) where ‘N’ is the length of the string.

 

Here, we are iterating over the entire Postfix expression which requires ‘N’ iterations, we push each element to the stack. Hence, our space complexity is O(N).

Code Solution
(100% EXP penalty)
PostFix To Prefix
Full screen
Console