# PostFix To Prefix

Posted: 24 Jun, 2021
Difficulty: Easy

## PROBLEM STATEMENT

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