Last Updated: 4 Apr, 2021

Infix To Postfix

Easy

Asked in companies

Solve now

Problem statement

You are given a string 'exp' which is a valid infix expression.

Convert the given infix expression to postfix expression.

Note:

Infix notation is a method of writing mathematical expressions in which operators are placed between operands. 

For example, "3 + 4" represents the addition of 3 and 4.

Postfix notation is a method of writing mathematical expressions in which operators are placed after the operands. 

For example, "3 4 +" represents the addition of 3 and 4.

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

Example:

Input: exp = ‘3+4*8’

Output: 348*+

Explanation:
Here multiplication is performed first and then the addition operation. Hence postfix expression is  3 4 8 * +.

Input Format:

The first line of input contains a string ‘exp’, a valid infix expression.

Output Format:

Return the valid postfix expression of the given infix expression.

Note:

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

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:
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)
While stack.size()
1. ‘ans’ += stack.back()
2. stack.pop()
Return ‘ans’.

Solve now