OJ Board

Posted: **Mon Feb 26, 2007 2:01 pm**

Arif vai, my accepted code returns

Output:

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.

Posted: **Mon Feb 26, 2007 3:47 pm**

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

Posted: **Mon Feb 26, 2007 4:31 pm**

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.

Posted: **Tue Feb 27, 2007 12:01 am**

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

Posted: **Sun Jul 22, 2007 1:30 pm**

can i have some more inputs for this problem.

Code: Select all

removed after AC

Posted: **Sun Jul 22, 2007 2:05 pm**

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

Posted: **Tue Sep 11, 2007 8:56 pm**

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

Code: Select all

Thanks, I got "Solved"

Posted: **Wed Sep 12, 2007 6:35 am**

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

Posted: **Fri Nov 07, 2008 5:32 am**

koalahong wrote: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.

Posted: **Sat May 16, 2009 6:09 am**

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.

Posted: **Sat Sep 01, 2012 8:21 pm**

someone can help me plz? getting WA.

Code: Select all

AC

Posted: **Thu Aug 18, 2016 3:12 am**

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"

OJ Board

551 - Nesting a Bunch of Brackets

can i hav some more inputs

Re: 551 Nesting a Bunch of Brackets WA

Re: 551 Nesting a Bunch of Brackets WA

Re: 551 Nesting a Bunch of Brackets WA

Re: 551 - Nesting a Bunch of Brackets