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.
Duplicate found in A/(B+C)*D : false Duplicate found in A/(B+C)*D/((E+F)) : true
Reference : this