균형 잡힌 표현식이 주어지면 중복된 괄호가 포함되어 있는지 확인하세요. 동일한 하위 표현식이 여러 개의 괄호로 묶인 경우 괄호 세트가 중복됩니다.
예:
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
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
산출
Duplicate Found
산출:
Duplicate Found시간 복잡도 위의 해는 O(n)입니다.
보조 공간 프로그램에서 사용하는 O(n)입니다.