SELVITÄ, ONKO LAUSEKKEESSA KAKSOISSULUT VAI EI

Kun tasapainoinen lauseke on annettu, selvitä, sisältääkö se kaksoissulut vai ei. Sulkeet ovat päällekkäisiä, jos samaa osalauseketta ympäröivät monisulut.

Esimerkkejä:

    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.

Voidaan olettaa, että annettu lauseke on kelvollinen eikä siinä ole välilyöntejä.

Ideana on käyttää pinoa. Iteroi annettua lauseketta ja lausekkeen jokaista merkkiä, jos merkki on avoin sulkumerkki '(' tai mikä tahansa operaattoreista tai operandiista, työnnä se pinon yläosaan. Jos merkki on sulkumerkki ')', ponnahtaa merkkejä pinosta, kunnes ne vastaavat avointa sulkumerkkiä '(' löytyy ja käytetään laskuria, jonka arvoa kasvatetaan, kunnes jokaisen merkin luku on havainnut. avauksen ja sulkemisen välillä kohdatut merkit sulkupari, joka on yhtä suuri kuin laskurin arvo, on pienempi kuin 1, niin kaksoissulkupari löytyy muuten ei esiinny redundantteja sulkupareja. Esimerkiksi (((a+b))+c) sisältää kaksoissulkeet 'a+b':n ympärillä. Kun toinen ')' a+b:n jälkeen kohdataan, pino sisältää '(('. Koska pinon yläosa on avaussulku, voidaan päätellä, että kaksoissulkeet.

Alla on yllä olevan idean toteutus:

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# 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

Lähtö

Duplicate Found

Lähtö:

Duplicate Found

Aika monimutkaisuus yllä olevasta ratkaisusta on O(n).

Aputila ohjelman käyttämä on O(n).

TechCodeview

Selvitä, onko lausekkeessa kaksoissulut vai ei