Opening and closing gates problem

Select Articles

Opening and closing gates problem

A water reservation system constructed in a city has several opening and closing gates. If any opening gates are not closed with a corresponding closing gate then the water will leak out of the system and there will be a threat to the life of people living in the city. Also, the closing gate cannot exist without the opening gate, so the system head checks the design of the system and he has to ensure that the people are safe in the city. Write an algorithm to find whether people are safe or not.

 

Input:

The input to the function/method consists of one argument - str, a string representing the sequence of gates of the water reservation system.

 

Output:

Return an integer representing the number of gates which have closing gates corresponding to the opening gates else return an integer -1.

 

Constraints:

The opening gates are represented by '(' and closing gates are represented by ')'

 

Example 1

Input: Str = ()()

Output: 2

 

Logic:

This problem is like the balanced parenthesis problem. Once a pair of parenthesis is found (the pair should have an opening parenthesis and closing parenthesis), a counter is incremented.

 

Solution to opening and closing gates problem

This question was asked in the recruitment drive of companies like Wipro.

 

C

#include

int top = -1,c=0;

char stack[100];

// function prototypes

void push(char);

void pop();

void find_top();

int main()

{

int i;

char a[100];

printf(“enter expression\n”);

scanf(“%s”, &a);

for (i = 0; a[i] != ‘\0’;i++)

{

if (a[i] == ‘(‘)

{

push(a[i]);

}

else if (a[i] == ‘)’)

{

pop();

}

}

find_top();

return 0;

}

// to push elements in stack

void push(char a)

{

stack[top] = a;

top++;

}

// to pop elements from stack

void pop()

{

if (top == -1)

{

printf(“-1”);

exit(0);

}

else

{

top–;

c++;

}

}

// to find top element of stack

void find_top()

{

if (top == -1)

printf(“%d”,c);

else

printf(“-1”);

}

 

C++

#include

#include             //to use strlen(), we need to include this header

using namespace std;

char st[20];

int top=-1;

void push(char a)

{

   st[++top]=a;

}

char pop()

{

   return st[top–];

}

int main()

{

   char a[20],t;

   int i,f=1;

   int count=0;

   cout<<“Enter the String: “;

   cin>>a;

   for(i=0;i

   {

       if(a[i]=='(‘)

           push(a[i]);

       if(a[i]==’)’)

       {

           if(top==-1)

               f=0;

           else

           {

               t=pop();

               if(t=='(‘)

                   count++;

           }

       }

   }

   

if(top>=0)

 f=0;

if(f==0)

 cout<<“-1”;

else

 cout<<“Count: “<

return 0;

}

 

JAVA

import java.util.Scanner;

import java.util.*;

public class Main

{

   public static int isParenthesisMatch(String str)

   {

       Stack stack = new Stack();

       int count = 0;

       char c;

       for(int i=0; i < str>

       {

           c = str.charAt(i);

           if(c == ‘(‘)

               stack.push(c);

 

           if(c == ‘)’)

           {

               if(stack.empty())

               {

                   count = -1;

                   return count;

               }

               else if(stack.peek() == ‘(‘)

               {

                   count++;

                   stack.pop();

               }

               else

                   return count;

           }     

           }

       return count;

   }

   public static void main(String args[])  

   {

Scanner sc = new Scanner(System.in);

System.out.println(“Enter the string: “);

String str = sc.nextLine();

   System.out.println(isParenthesisMatch(str));

   }

}

 

PYTHON 3 

s = input(“Enter the string: “)

flag = 1

count = 0

stack = []

for x in s:

   if x == ‘(‘:

       stack.append(x)

   if x == ‘)’:

       if stack == []:

           flag = 0

           break

       t = stack.pop()

       if t != ‘(‘:

           flag = 0

           break

       else:

           count = count+1            

if flag == 1:

   print(“Count: %d” %(count))

else:

   print(“-1”)

 

Output

Input- Enter the String: () ((())) () Output- 5 Input- Enter the string () () (()) Output- 4