Gegeven een gebalanceerde uitdrukking, zoek of deze dubbele haakjes bevat of niet. Een reeks haakjes is duplicaat als dezelfde subexpressie is omgeven door meerdere haakjes.
Voorbeelden:
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.
Er mag worden aangenomen dat de gegeven uitdrukking geldig is en dat er geen spaties aanwezig zijn.
Het idee is om stapel te gebruiken. Herhaal de gegeven expressie en voor elk teken in de uitdrukking als het teken een open haakje '(' is of een van de operatoren of operanden duwt het naar de bovenkant van de stapel. Als het teken een haakje ')' is, verwijder dan tekens uit de stapel tot het overeenkomende haakje '(' wordt gevonden en er wordt een teller gebruikt waarvan de waarde wordt verhoogd voor elk aangetroffen teken tot het haakje openen '(' is gevonden. Als het aantal tekens is gevonden tussen het openen en sluiten Het haakjespaar dat gelijk is aan de waarde van de teller is kleiner dan 1, dan wordt er een paar dubbele haakjes gevonden, anders komen er geen overtollige haakjesparen voor. (((a+b))+c) heeft bijvoorbeeld dubbele haakjes rond 'a+b'. Wanneer de tweede ')' na a+b wordt aangetroffen, bevat de stapel '(('. Omdat de bovenkant van de stapel een openingshaakje is, kan worden geconcludeerd dat er dubbele haakjes.
Hieronder ziet u de implementatie van bovenstaand idee:
C++
// C++ program to find duplicate parenthesis in a // balanced expression #include
import java.util.Stack; // Java program to find duplicate parenthesis in a // balanced expression public class GFG { // Function to find duplicate parenthesis in a // balanced expression static boolean findDuplicateparenthesis(String s) { // create a stack of characters Stack<Character> Stack = new Stack<>(); // Iterate through the given expression char[] str = s.toCharArray(); for (char ch : str) { // if current character is close parenthesis ')' if (ch == ')') { // pop character from the stack char top = Stack.peek(); Stack.pop(); // stores the number of characters between a // closing and opening parenthesis // if this count is less than or equal to 1 // then the brackets are redundant else not int elementsInside = 0; while (top != '(') { elementsInside++; top = Stack.peek(); Stack.pop(); } if (elementsInside < 1) { return true; } } // push open parenthesis '(' operators and // operands to stack else { Stack.push(ch); } } // No duplicates found return false; } // Driver code public static void main(String[] args) { // input balanced expression String str = '(((a+(b))+(c+d)))'; if (findDuplicateparenthesis(str)) { System.out.println('Duplicate Found '); } else { System.out.println('No Duplicates Found '); } } }
# Python3 program to find duplicate # parenthesis in a balanced expression # Function to find duplicate parenthesis # in a balanced expression def findDuplicateparenthesis(string): # create a stack of characters Stack = [] # Iterate through the given expression for ch in string: # if current character is # close parenthesis ')' if ch == ')': # pop character from the stack top = Stack.pop() # stores the number of characters between # a closing and opening parenthesis # if this count is less than or equal to 1 # then the brackets are redundant else not elementsInside = 0 while top != '(': elementsInside += 1 top = Stack.pop() if elementsInside < 1: return True # push open parenthesis '(' operators # and operands to stack else: Stack.append(ch) # No duplicates found return False # Driver Code if __name__ == '__main__': # input balanced expression string = '(((a+(b))+(c+d)))' if findDuplicateparenthesis(string) == True: print('Duplicate Found') else: print('No Duplicates Found') # This code is contributed by Rituraj Jain
// C# program to find duplicate parenthesis // in a balanced expression using System; using System.Collections.Generic; class GFG { // Function to find duplicate parenthesis // in a balanced expression static Boolean findDuplicateparenthesis(String s) { // create a stack of characters Stack<char> Stack = new Stack<char>(); // Iterate through the given expression char[] str = s.ToCharArray(); foreach (char ch in str) { // if current character is // close parenthesis ')' if (ch == ')') { // pop character from the stack char top = Stack.Peek(); Stack.Pop(); // stores the number of characters between // a closing and opening parenthesis // if this count is less than or equal to 1 // then the brackets are redundant else not int elementsInside = 0; while (top != '(') { elementsInside++; top = Stack.Peek(); Stack.Pop(); } if (elementsInside < 1) { return true; } } // push open parenthesis '(' // operators and operands to stack else { Stack.Push(ch); } } // No duplicates found return false; } // Driver code public static void Main(String[] args) { // input balanced expression String str = '(((a+(b))+(c+d)))'; if (findDuplicateparenthesis(str)) { Console.WriteLine('Duplicate Found '); } else { Console.WriteLine('No Duplicates Found '); } } } // This code is contributed by 29AjayKumar
// JavaScript program to find duplicate parentheses in a balanced expression function findDuplicateParenthesis(s) { let stack = []; // Iterate through the given expression for (let ch of s) { // If current character is a closing parenthesis ')' if (ch === ')') { let top = stack.pop(); // Count the number of elements // inside the parentheses let elementsInside = 0; while (top !== '(') { elementsInside++; top = stack.pop(); } // If there's nothing or only one element // inside it's redundant if (elementsInside < 1) { return true; } } // Push open parenthesis '(' operators and operands to stack else { stack.push(ch); } } // No duplicates found return false; } // Driver code let str = '(((a+(b))+(c+d)))'; if (findDuplicateParenthesis(str)) { console.log('Duplicate Found'); } else { console.log('No Duplicates Found'); } // This code is contributed by rag2127
Uitvoer
Duplicate Found
Uitgang:
Duplicate FoundTijdcomplexiteit van bovenstaande oplossing is O(n).
Hulpruimte gebruikt door het programma is O(n).