Adott egy kiegyensúlyozott kifejezés, keresse meg, hogy tartalmaz-e duplikált zárójelet vagy sem. Egy zárójelkészlet duplikált, ha ugyanazt a részkifejezést többszörös zárójel veszi körül.
Példák:
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.
Feltételezhető, hogy az adott kifejezés érvényes, és nincsenek szóközök.
java priorityqueue
Az ötlet a verem használata. Iteráljon a megadott kifejezésen és a kifejezés minden karakterénél, ha a karakter nyitott zárójel '(' vagy bármely operátor vagy operandus, tolja a verem tetejére. Ha a karakter zárt zárójel ')', akkor a karakterek a veremből a '(') megfelelő nyitott zárójelig ugrik ki, és egy számláló kerül felhasználásra, amelynek értéke a nyitó zárójelig növekszik. karakterek, amelyek a nyitás és a között találkoztak a számláló értékével egyenlő záró zárójelpár kisebb, mint 1, akkor a rendszer duplikált zárójelpárt talál, különben nem fordul elő redundáns zárójelpár. Például az ((a+b))+c) duplikált zárójeleket tartalmaz az „a+b” körül. Ha az a+b utáni második ')' jelet találja, a verem tartalmazza a '(('. Mivel a verem teteje egy nyitó zárójel, ezért arra lehet következtetni hogy duplikált zárójelek vannak.
Alább látható a fenti ötlet megvalósítása:
kat timpf magasságC++
// 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
Kimenet
Duplicate Found
Kimenet:
Duplicate FoundIdőbeli összetettség a fenti megoldás O(n).
Segédtér a program által használt O(n).
csma és csma cd