Last Updated: 24 Oct, 2021
Duplicate Parenthesis
Moderate
Asked in companies
You are given the expression ‘expr’ with parenthesis. Your task is to find if the given expression contains duplicate parenthesis. A set of parenthesis is duplicate if multiple parenthesis surrounds the same subexpression.
For Example:
You are given ‘expr’ = “(a+b)+((c+d))”, here the subexpression “c+d” is surrounded by two parentheses. Hence the expression contains duplicate parenthesis. Hence the answer is “YES”.
Input Format:
The first line of input contains a single integer ‘T’, representing the number of test cases.
The first line of each test case contains a string, ‘expr’, representing the given expression.
Output Format:
For each test case, print “YES” if the expression contains a duplicate parenthesis. Otherwise, print “NO”.
Print a single line for each test case.
Constraints:
1 <= T <= 10
1 <= |expr| <= 10^6
Time Limit: 1 sec
Note:
You do not need to print anything. It has already been taken care of. Just implement the function.
Approaches
In this approach, we will use the stack data structure and iterate through every character in the expression of the character is not a closed parenthesis ( ( ) then, we push it to the top of the stack. Otherwise, if a closing parenthesis is found we pop the stack until a ‘(‘ is found. If the number of characters between the parenthesis is not greater than 1 then return false. Otherwise, return true.
Algorithm:
- Initialise an empty stack st.
- Iterate ch through expr
- If ch is not ), then insert ch into st
- Otherwise,
- Set top as the top of the st and pop the st
- Set counter as 0
- While top of the stack is not equal to (
- Pop the stack st
- Increase counter by 1
- If the counter is less than 1 return true
- Return false