Last Updated: 24 Jun, 2021

PostFix To Prefix

Easy

Asked in companies

Solve now

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.

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.

Solve now

Approaches

01 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.

Solve now