بالنظر إلى تعبير متوازن، ابحث عما إذا كان يحتوي على أقواس مكررة أم لا. تتكرر مجموعة الأقواس إذا كان نفس التعبير الفرعي محاطًا بأقواس متعددة.
أمثلة:
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.
يمكن الافتراض أن التعبير المحدد صالح ولا توجد أية مسافات بيضاء.
الفكرة هي استخدام المكدس. قم بالتكرار من خلال التعبير المحدد ولكل حرف في التعبير إذا كان الحرف عبارة عن قوس مفتوح '(' أو أي من العوامل أو المعاملات يدفعه إلى أعلى المكدس. إذا كان الحرف بين قوسين قريبين ')'، فسيتم العثور على أحرف من المكدس حتى مطابقة القوس المفتوح '(' ويتم استخدام عداد تتزايد قيمته لكل حرف يتم مواجهته حتى يتم العثور على قوس الفتح '('. إذا كان عدد الأحرف التي تمت مواجهتها بين زوج قوسي الفتح والإغلاق والتي تساوي قيمة العداد أقل من 1 ثم يتم العثور على زوج من الأقواس المكررة وإلا فلن يحدث أي أزواج أقواس زائدة عن الحاجة. على سبيل المثال، يحتوي (((a+b))+c) على أقواس مكررة حول 'a+b'. عند مواجهة ')' الثانية بعد a+b، تحتوي المكدس على '(('. نظرًا لأن الجزء العلوي من المكدس عبارة عن قوس مفتوح، فيمكن استنتاج أن هناك أقواسًا مكررة.
وفيما يلي تنفيذ الفكرة المذكورة أعلاه:
C++
// C++ program to find duplicate parenthesis in a // balanced expression #include using namespace std; // Function to find duplicate parenthesis in a // balanced expression bool findDuplicateparenthesis(string str) { // create a stack of characters stack<char> Stack; // Iterate through the given expression for (char ch : str) { // if current character is close parenthesis ')' if (ch == ')') { // pop character from the stack char top = 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 int elementsInside = 0; while (top != '(') { elementsInside++; top = Stack.top(); Stack.pop(); } if(elementsInside < 1) { return 1; } } // push open parenthesis '(' operators and // operands to stack else Stack.push(ch); } // No duplicates found return false; } // Driver code int main() { // input balanced expression string str = '(((a+(b))+(c+d)))'; if (findDuplicateparenthesis(str)) cout << 'Duplicate Found '; else cout << 'No Duplicates Found '; return 0; }
Java 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 '); } } }
Python # 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# // 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 // 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
الإخراج
Duplicate Found
الإخراج:
Duplicate Foundتعقيد الوقت الحل أعلاه هو O(n).
مساحة مساعدة المستخدم من قبل البرنامج هو O(n).