551 - Nesting a Bunch of Brackets

[Jan]

Arif vai, my accepted code returns

Output:

Code: Select all

YES
NO 7
NO 17
NO 3
YES
YES
YES
NO 9
YES
YES
YES
YES
YES
YES
NO 2
NO 3
NO 6

Hope these help.

[arif_pasha]

Thanks Jan for your reply.
My Output:

Code: Select all

YES
NO 8
NO 8
NO 2
YES
YES
YES
NO 4
YES
YES
YES
YES
YES
YES
NO 2
NO 2
NO 6

I dont understand the output for the following inputs, can u explain those..

Code: Select all

input                              your_output
({{}{}}[{(){}[]}                   NO 17
aaa(aaaa                           NO 9  

[Jan]

We will report when we are sure that we have found something wrong.

Input:

Code: Select all

aaa(aaaa

After 'aaa(', we are not sure about the correctness. Because 'aaa()' is correct. After 'aaa(aaa', we are still not sure, because 'aaa(aaa)' is correct.

But after 'aaa(aaaa', we have found no other character, but we were expecting a ')'. Thats why we are sure that its an error.

Thats all I can remember. Hope these help.

[arif_pasha]

Thanks JAN. your output and explanation was really helpful.
I got AC at last.

[spider_6765]

can i have some more inputs for this problem.

Code: Select all

removed after AC

[Jan]

Some cases are posted already and your code fails for some of them.

[ashis.csedu]

Can anyone tell me what is wrong with my code? or provide some critical I/O....

Code: Select all

Thanks, I got "Solved"

[ashis.csedu]

Forget that, I've solved the bug.
I guess there are cases like the following -

Code: Select all

Input:
(*a++(*)
(*a{+}*)
    <************)>
    ()(***)(**)
   ()(***)(*)
({{}{}}[{(){}[]}
   ([))
 ()(**)
    ()*
 aaaaaaa
    aaa(aaaa
 *******
    a*a*a*a
  ()a
 a()
  ()*()
  (*a{+}*)
  **)
 *(*
  (*a++(*)

Code: Select all

Output:
NO 6
YES
NO 13
YES
NO 7
NO 17
NO 3
YES
YES
YES
NO 9
YES
YES
YES
YES
YES
YES
NO 2
NO 3
NO 6

In my previous code I replaced

Code: Select all

while(gets(input)){
      ....
      ....
}

with this one -

Code: Select all

while(scanf("%s",input)==1){
      ....
      ....
}

to take input and got "solved". Thanks

[DD]

I have tried all of input data in all of relative threads. Problem is maybe that when the last line is a blank line , my program will terminate without print "YES". Can anyone tell me how to solve this situation? Thx a lot !

Code: Select all

#include<iostream>
#include<string>
#include<stack>

using namespace std;

int main()
{
	stack<int> bracket[5];	//0 to 4 (), [], {}, <>, (**)
	char exp[3001];
	int offset, i;
	bool error;
	
	while(cin.getline(exp, 3000)!=NULL){
        
		offset=1;
		error = false;

               //initial stacks
		for(i=0 ; i<5 ; i++)
			while(!bracket[i].empty())
				bracket[i].pop();

		for(i=0 ; exp[i]!='\0' ; i++){
        	switch(exp[i]){
			case '(':
				if(exp[i+1]=='*'){
					bracket[4].push(offset);
					offset++;
					i++;
				}
				else{
					bracket[0].push(offset);
					offset++;
				}
				break;
			case ')':
				if(bracket[0].empty()){
					cout << "NO " << offset << endl;
					error = true;
				}
				else{
					bracket[0].pop();
					offset++;
				}
				break;
			case '*':
				if(exp[i+1]==')'){
					if(bracket[4].empty()){
						cout << "NO " << offset << endl;
						error = true;
					}
					else{
						bracket[4].pop();
						offset++;
						i++;
					}
				}
				else{
					offset++;
				}
				break;
			case '[':
				bracket[1].push(offset);
				offset++;
				break;
			case ']':
				if(bracket[1].empty()){
					cout << "NO " << offset << endl;
					error = true;
				}
				else{
					bracket[1].pop();
					offset++;
				}
				break;
			case '{':
				bracket[2].push(offset);
				offset++;
				break;
			case '}':
				if(bracket[2].empty()){
					cout << "NO " << offset << endl;
					error = true;
				}
				else{
					bracket[2].pop();
					offset++;
				}
				break;
			case '<':
				bracket[3].push(offset);
				offset++;
				break;
			case '>':
				if(bracket[3].empty()){
					cout << "NO " << offset << endl;
					error = true;
				}
				else{
					bracket[3].pop();
					offset++;
				}
				break;
			default:
				offset++;
				break;
			}// end switch
			
			if(error){
                break;
            }
		}// end for

	      //if no error check all stack are empty or not
               if(!error){
			for(i=0 ; i<5 ; i++){
				if(!bracket[i].empty()){
					cout << "NO " << offset << endl;
					break;
				}
			}
                        //all stacks are empty
			if(i==5)
			    cout << "YES" << endl;
		}
	}

	return 0;
}

Hi,

Try this input:

Code: Select all

#!^$!^<><>{[<[}]>

The correct output is:

Code: Select all

NO 15

And your porgram output is:

Code: Select all

NO 18

Hope this can help.

[alamgir kabir]

I am getting WA a huge number of times. Please anyone help me.
Give me some special I/O that I find my fault.
My code is given below.

Code: Select all

#include<stdio.h>
#include<string.h>
#include "alloc.h"
#include<stdlib.h>

char str [ 4000 ], sp [ 4000 ];

struct stk
{
    char data;
    struct stk *next;
};

void push( struct stk **st, int item )
{
    struct stk *s;
    s = (stk*) malloc( sizeof( struct stk ) );
    s -> data = item;
    s -> next = *st;
    *st = s;
    return;
}

char pop(struct stk **st)
{
    char item;
    struct stk *s;

    if( *st != NULL )
    {
        s = *st;
        item = s -> data;
        *st = s -> next;
        free( s );
        return item;
    }
    return '-';
}



int main()
{
    int i, j, count;
    bool correct;
    char item;

    while( gets( str ) )
    {
        for( i = 0, j = 0; str [ i ] != '\0'; i ++)
        {
            if( str [ i ] == '(' )
            {
                if( str [ i + 1 ] == '*' )
                {
                    i ++;
                    sp [ j ++ ] = '1';
                }
                else
                {
                    sp [ j ++ ] = '(';
                }
                continue;
            }
            if( str [ i ] == '*' )
            {
                if( str [ i + 1 ] == ')' )
                {
                    i ++;
                    sp [ j ++ ] = '2';
                }
                else
                {
                    sp [ j ++ ] = '3';
                }
                continue;
            }
            if( str [ i ] == '{' || str [ i ] == '}' || str [ i ] == '<' || str [ i ] == '>' || str [ i ] == '[' || str [ i ] == ']' || str [ i ] == ')')
            {
                sp [ j ++ ] = str [ i ];
                continue;
            }
            sp [ j ++ ] = '3';
        }
        sp [ j ] = '\0';
        //printf("%s\n", sp);
        struct stk *top = NULL;
        correct = true;
        count = 0;

        for( i = 0; sp [ i ] != '\0'; i ++ )
        {
            //printf("%c", sp [ i ]);
            count ++;
            if( sp [ i ] == '(' || sp [ i ] == '1' || sp [ i ] == '{' || sp [ i ] == '[' || sp [ i ] == '<')
            {
                push( &top, sp [ i ] );
            }
            else
            {
                if( sp [ i ] == ')' || sp [ i ] == '2' || sp [ i ] == '}' || sp [ i ] == ']' || sp [ i ] == '>')
                {
                    item = pop( &top );

                    if( item == '-' )
                    {
                        correct = false;
                        break;
                    }
                    if( item == '(' && sp [ i ] != ')')
                    {
                        correct = false;
                        break;
                    }
                    if( item == '1' && sp [ i ] != '2')
                    {
                        correct = false;
                        break;
                    }
                    if( item == '{' && sp [ i ] != '}')
                    {
                        correct = false;
                        break;
                    }
                    if( item == '[' && sp [ i ] != ']')
                    {
                        correct = false;
                        break;
                    }
                    if( item == '<' && sp [ i ] != '>')
                    {
                        correct = false;
                        break;
                    }
                }
            }
        }

        if( correct && top == NULL )
        {
            printf("YES\n");
        }
        else
        {
            printf("NO %d\n", count);
        }
    }
    return 0;
}

Thanks everybody.

[Scarecrow]

someone can help me plz? getting WA.

Code: Select all

AC

[metaphysis]

Poor problem statement.
"but if you reach the end of a test case and not find an expression not properly nested and some brackets are even opened you must print number_of_chars_of_the_case + 1"