# Infix To Postfix

Posted: 4 Apr, 2021

Difficulty: Easy

#### You are given a string EXP which is a valid infix expression. Convert the given infix expression to postfix expression.

#### Infix expression is of the form a op b. Where operator is is between the operands.

#### Postfix expression is of the form a b op. where the operator is after the operands.

#### Infix expression link

#### Postfix expression link

##### Expression contains digits, lower case English letters, ‘(’, ‘)’, ‘+’, ‘-’, ‘*’, ‘/’, ‘^’.

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

- ANS = ’’
- stack=[]
- precedence is a hashmap that stores the precedence of the valid operators.
- For char in expression
- If isOperand(char)
- This isOperand is a function that checks if the ‘char’ is a lower case English character or a digit
- ANS +=char

- If char == ‘)’
- We encounter a closing bracket so we have to pop till an opening bracket
- While stack.back()!=’(’
- ANS+=stack.back()
- stack.pop()

- stack.pop()

- If char ‘(’
- stack.push(char)

- Else
- While stack.size() and precedence[stack.back()] >= precedence[char]
- ANS+=stack.back()
- stack.pop()

- stack.push(char)

- While stack.size() and precedence[stack.back()] >= precedence[char]

- If isOperand(char)
- While stack.size()
- ANS+=stack.back()
- stack.pop()

- Return ANS

SIMILAR PROBLEMS

# Magical String

Posted: 27 Apr, 2021

Difficulty: Easy

# Span of Ninja Coin

Posted: 27 Apr, 2021

Difficulty: Moderate

# Queries on Stack

Posted: 28 Apr, 2021

Difficulty: Moderate

# PostFix To Prefix

Posted: 24 Jun, 2021

Difficulty: Easy

# Implement a Queue

Posted: 27 Jul, 2021

Difficulty: Easy