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. 


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. 

Complete Code: 


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

Reference : this

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

%d bloggers like this: