PostFix To Prefix

Posted: 24 Jun, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

Ninja has been given a Postfix expression and he needs your help in converting it to Prefix expression.

Postfix expression is an expression where the operator appears in the expression after the operands. Simply of the form (operand1 operand2 operator)

Prefix expression is an expression where the operator appears in the expression before the operands. Simply of the form (operator operand1 operand2)

For Example:

Postfix expression : (A B +)

Prefix expression : (+ A B)
Input Format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains a string ‘S’ which contains the Postfix expression.
Output Format:
For each case, you need to return a string in the prefix expression.

The output of each test case will be printed in a separate line.
Note:
You do not need to input or print anything, and it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= |S| <= 10^5

Timit Limit: 1 sec
Approach 1

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.
Try Problem