How to find the correct brackets sequence?

Question

I've to figure it out that the bracket sequence is correct. Here is my problem. Neat bracket

& Here is my solution code.

#include <stdio.h>
int main()
{
    char s[100];
    int c=0,count1=0,count2=0,count3=0;
    scanf("%[^\n]",s);
    while(s[c] !='\0')
        {
        if(s[c] == '(')
        {
            ++count1;
        }
        if(s[c] == ')')
        {
            ++count2;
        }
        if(s[c] == '"')
        {
            ++count3;
        }
        ++c;
    }
    if(count1==count2 && count3%2 ==0)
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
    return 0;
}

But it returns incorrect answer for a test case. & I also know that the algorithm is not proper 'cause it fails to give the correct answer for this test case

)))""(((

So how can I improve my algorithm???

Answer 1

Ok. I've done. Here is my solve. Thanks to " max66 ". So in this problem , you've to identify one most important thing that ")" isn't used without its closing tags. That's I've done. Here is my solution.

#include <stdio.h>
int main()
{
    int c=0,count1=0,count2=0;
    char s[1000];
    scanf("%[^\n]",s);
    while(s[c] != '\0')
    {
        if(s[c] == '"')
        {
            ++count2;
        }
        if(s[c] == ')')
        {
            --count1;
        }
        if (count1 != -1)
        {
            if(s[c]== '(')
            {
               ++count1;
            }
        }

        ++c;
    }
    ///printf("%d\n",count1);
    ///printf("%d\n",count2);
    if(count1 == 0 && count2%2 == 0)
    {
        printf("Every thing is OK!\n");
    }
    else
    {
        printf("Something is fishy!\n");
    }
    return 0;
}

Answer 2

Do it with std::stack. Idea is to

1. If stack is empty, push s[i] to stack.
2. Compare current character aka s[i] with stack.top() and pop stack if does match.
3. Push current character aka s[i] onto stack when no match is found.

Assume input is : "()(())". Now,

A. i = 0. Initially stack is empty. Push "(" on stack. Stack - "(".

B. i = 1. Stack is not empty. Compare ")" aka s1 with stack's top - "(". It does match. Now, pop stack. Stack - "".

C. i = 2. Now stack is empty. Push "(" on stack. Stack - "(".

D. i = 3. Stack is not empty. Compare "(" aka s[3] with stack's top - ")". It does not match. Now, push "(" to stack. Stack - "(("

E. i = 4. Stack is not empty. Compare ")" aka s[4] with stack's top - "(". It does match. Now, pop stack. Stack - "("

F. i = 5. Stack is not empty. Compare ")" aka s[5] with stack's top - "(". It does match. Now, pop stack. Stack - ""

Now, Stack is empty, We can say string is neat - as mentioned in question. Had we left with any unmatched parenthesis in stack, that'd mean string is not neat.

     //Assuming s is the char array containing parenthesis sequence.
     int i = 0;
     std::stack<char> st;
     while(s[i] != '\0') //Better choice would be to use std::string
     {
        if(st.empty() )
        {
             st.push( s[i++] ); 
             continue;
        } 
        if( st.top() == '(' && s[i] == ')' )
            { st.pop(); i++ }
        else
            st.push(s[i++]);   

      }
       if(st.empty() )  
          printf("Yes");
       else 
          printf("No");