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. 

Complete Code:

Output: 

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

Reference : this

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: