# Infix To Postfix

Posted: 4 Apr, 2021
Difficulty: Easy

## PROBLEM STATEMENT

#### For example:

``````EXP = ‘3+4*8’
Here multiplication is performed first and then the addition operation
ANS = 3 4 8 * +
``````
##### Input Format:
``````The first line of input contains an integer T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains a string ‘EXP’, a valid infix expression.
``````
##### Output Format:
``````For each query print, the valid postfix expression of the given infix expression.

Output for each query is printed in a separate line.
``````
##### Note:
``````You don’t need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 10
1 <= N <= 5000

‘N’, is the length of EXP
The expression contains digits, lower case English letters, ‘(’, ‘)’, ‘+’, ‘-’, ‘*’, ‘/’, ‘^’.

Time Limit: 1 sec
`````` Approach 1

We will scan the expression from left to write and if we encounter an operand we will append it to our answer. If we encounter an operator we will pop all the operators with equal or higher precedence and append them to our answer. And push the current operator. In the end, we will empty the stack.

Order of precedence = [ ‘^’, ‘*’ and ‘/’, ‘+’ and ‘-’, ‘(’, ‘)’]

Order of precedence [ link ]

The algorithm will be-

1. ANS = ’’
2. stack=[]
3. precedence is a hashmap that stores the precedence of the valid operators.
4. For char in expression
1. If isOperand(char)
1. This isOperand is a function that checks if the ‘char’ is a lower case English character or a digit
2. ANS +=char
2. If char == ‘)’
1. We encounter a closing bracket so we have to pop till an opening bracket
2. While stack.back()!=’(’
1. ANS+=stack.back()
2. stack.pop()
3. stack.pop()
3. If char ‘(’
1. stack.push(char)
4. Else
1. While stack.size() and precedence[stack.back()] >= precedence[char]
1. ANS+=stack.back()
2. stack.pop()
2. stack.push(char)
5. While stack.size()
1. ANS+=stack.back()
2. stack.pop()
6. Return ANS