Find if an expression has duplicate parenthesis or not
Last Updated :
16 Feb, 2023
Given a balanced expression, find if it contains duplicate parenthesis or not. A set of parenthesis are duplicate if the same subexpression is surrounded by multiple parenthesis.
Examples:
Below expressions have duplicate parenthesis -
((a+b)+((c+d)))
The subexpression "c+d" is surrounded by two
pairs of brackets.
(((a+(b)))+(c+d))
The subexpression "a+(b)" is surrounded by two
pairs of brackets.
(((a+(b))+c+d))
The whole expression is surrounded by two
pairs of brackets.
((a+(b))+(c+d))
(b) and ((a+(b)) is surrounded by two
pairs of brackets but, it will not be counted as duplicate.
Below expressions don't have any duplicate parenthesis -
((a+b)+(c+d))
No subexpression is surrounded by duplicate
brackets.
It may be assumed that the given expression is valid and there are not any white spaces present.
The idea is to use stack. Iterate through the given expression and for each character in the expression, if the character is a open parenthesis ‘(‘ or any of the operators or operands, push it to the top of the stack. If the character is close parenthesis ‘)’, then pop characters from the stack till matching open parenthesis ‘(‘ is found and a counter is used, whose value is incremented for every character encountered till the opening parenthesis ‘(‘ is found. If the number of characters encountered between the opening and closing parenthesis pair, which is equal to the value of the counter, is less than 1, then a pair of duplicate parenthesis is found else there is no occurrence of redundant parenthesis pairs. For example, (((a+b))+c) has duplicate brackets around “a+b”. When the second “)” after a+b is encountered, the stack contains “((“. Since the top of stack is a opening bracket, it can be concluded that there are duplicate brackets.
Below is the implementation of above idea :
C++
#include <bits/stdc++.h>
using namespace std;
bool findDuplicateparenthesis(string str)
{
stack<char> Stack;
for (char ch : str)
{
if (ch == ')')
{
char top = Stack.top();
Stack.pop();
int elementsInside = 0;
while (top != '(')
{
elementsInside++;
top = Stack.top();
Stack.pop();
}
if(elementsInside < 1) {
return 1;
}
}
else
Stack.push(ch);
}
return false;
}
int main()
{
string str = "(((a+(b))+(c+d)))";
if (findDuplicateparenthesis(str))
cout << "Duplicate Found ";
else
cout << "No Duplicates Found ";
return 0;
}
|
Java
import java.util.Stack;
public class GFG {
static boolean findDuplicateparenthesis(String s) {
Stack<Character> Stack = new Stack<>();
char[] str = s.toCharArray();
for (char ch : str) {
if (ch == ')') {
char top = Stack.peek();
Stack.pop();
int elementsInside = 0;
while (top != '(') {
elementsInside++;
top = Stack.peek();
Stack.pop();
}
if (elementsInside < 1) {
return true;
}
}
else {
Stack.push(ch);
}
}
return false;
}
public static void main(String[] args) {
String str = "(((a+(b))+(c+d)))";
if (findDuplicateparenthesis(str)) {
System.out.println("Duplicate Found ");
} else {
System.out.println("No Duplicates Found ");
}
}
}
|
Python3
def findDuplicateparenthesis(string):
Stack = []
for ch in string:
if ch == ')':
top = Stack.pop()
elementsInside = 0
while top != '(':
elementsInside += 1
top = Stack.pop()
if elementsInside < 1:
return True
else:
Stack.append(ch)
return False
if __name__ == "__main__":
string = "(((a+(b))+(c+d)))"
if findDuplicateparenthesis(string) == True:
print("Duplicate Found")
else:
print("No Duplicates Found")
|
C#
using System;
using System.Collections.Generic;
class GFG
{
static Boolean findDuplicateparenthesis(String s)
{
Stack<char> Stack = new Stack<char>();
char[] str = s.ToCharArray();
foreach (char ch in str)
{
if (ch == ')')
{
char top = Stack.Peek();
Stack.Pop();
int elementsInside = 0;
while (top != '(')
{
elementsInside++;
top = Stack.Peek();
Stack.Pop();
}
if (elementsInside < 1)
{
return true;
}
}
else
{
Stack.Push(ch);
}
}
return false;
}
public static void Main(String[] args)
{
String str = "(((a+(b))+(c+d)))";
if (findDuplicateparenthesis(str))
{
Console.WriteLine("Duplicate Found ");
}
else
{
Console.WriteLine("No Duplicates Found ");
}
}
}
|
Javascript
<script>
function findDuplicateparenthesis(s)
{
let Stack = [];
let str = s.split("");
for(let ch = 0; ch < str.length;ch++)
{
if (str[ch] == ')')
{
let top = Stack.pop();
let elementsInside = 0;
while (top != '(')
{
elementsInside++;
top = Stack.pop();
}
if (elementsInside < 1)
{
return true;
}
}
else
{
Stack.push(str[ch]);
}
}
return false;
}
let str = "(((a+(b))+(c+d)))";
if (findDuplicateparenthesis(str))
{
document.write("Duplicate Found ");
}
else
{
document.write("No Duplicates Found ");
}
</script>
|
Output:
Duplicate Found
Time complexity of above solution is O(n).
Auxiliary space used by the program is O(n).
Please Login to comment...