Infix To Postfix

Posted: 4 Apr, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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-

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