Be the first user to complete this post

  • 0
 Add to List
Medium

402. Check if Arithmetic Expression contains duplicate parenthesis

Objective: Given an arithmetic expression, write an algorithm to find out whether the expression contains duplicate parenthesis.

Duplicate Parenthesis: Two contiguous parentheses with no elements between them can be called as duplicate parenthesis. 

Example:

Input: A/(B+C)*D
Output: No duplicate parenthesis found.

Input: A/(B+C)*D/((E+F))
Output: duplicate parenthesis found

Approach: Use Stack

  • Iterate the given expression from left to right, one character at a time. 
  • If the character is not ")", push it to stack.
  • If a character is ")", then pop from the stack until "("open parenthesis is not encountered and keep counting the popped characters. 
  • Once open parenthesis is popped from stack check the count, if the count is less than 1 then we have found the duplicate parenthesis.  
  • look at the code below for more understanding. 

Output: 

Duplicate found in A/(B+C)*D : false
Duplicate found in A/(B+C)*D/((E+F)) : true

Reference : this

Related Problems: