Infix To Postfix

Easy
0/40
Average time to solve is 20m
104 upvotes
Asked in companies
DelhiverySamsungOracle

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 * +.


Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
3^(1+1)


Expected Answer:
311+^


Output printed on console:
311+^


Explanation of Sample Input 1:
For this testcase, we will evaluate 'b' = (1+1) first. 

Hence it's equivalent postfix expression will be "11+". 

Next we will evaluate 3^b. It's equivalent postfix expression will be "3b^". 

Replacing 'b' with it's equivalent postfix we get "311+^".


Sample Input 2:
a+b+c+d-e


Expected Answer:
ab+c+d+e-


Output printed on console:
ab+c+d+e-


Expected Time Complexity:
Try to do this in O(n).


Constraints:
1 <= 'n' <= 5000 

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

Time Limit: 1 sec
Hint

We will use the stack to store the encountered operators and consider them based on their order of precedence. 

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

Order of precedence

Approaches (1)
Stack

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’.
Time Complexity

O(n)  where ‘n’ is the length of the expression. 

Here, as we travel each character of the expression once, so iterate ‘n’ times. Hence, our time complexity is O(n).

Space Complexity

O(n)  where ‘n’ is the length of the expression.

Here, as we travel each character of the expression once, we store the elements in a stack that can store ‘n’ elements in at worst case. Hence, our space complexity is O(n).

Code Solution
(100% EXP penalty)
Infix To Postfix
Full screen
Console