551 - Nesting a Bunch of Brackets

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Feb 26, 2007 2:01 pm

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.
Ami ekhono shopno dekhi...
HomePage

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:

Post by arif_pasha » 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  

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » 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.
Ami ekhono shopno dekhi...
HomePage

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:

Post by arif_pasha » Tue Feb 27, 2007 12:01 am

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

spider_6765
New poster
Posts: 9
Joined: Sun Jan 08, 2006 9:57 pm

can i hav some more inputs

Post by spider_6765 » Sun Jul 22, 2007 1:30 pm

can i have some more inputs for this problem.

Code: Select all

removed after AC
Last edited by spider_6765 on Mon Jul 23, 2007 1:05 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Jul 22, 2007 2:05 pm

Some cases are posted already and your code fails for some of them.
Ami ekhono shopno dekhi...
HomePage

ashis.csedu
New poster
Posts: 12
Joined: Sat Aug 18, 2007 11:09 pm
Location: CSE, University of Dhaka

Post by ashis.csedu » 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"
Last edited by ashis.csedu on Wed Sep 12, 2007 6:35 am, edited 1 time in total.

ashis.csedu
New poster
Posts: 12
Joined: Sat Aug 18, 2007 11:09 pm
Location: CSE, University of Dhaka

Post by ashis.csedu » 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

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 551 Nesting a Bunch of Brackets WA

Post by DD » 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. 8)
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

alamgir kabir
New poster
Posts: 37
Joined: Wed Oct 03, 2007 10:42 am

Re: 551 Nesting a Bunch of Brackets WA

Post by alamgir kabir » 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.

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 551 Nesting a Bunch of Brackets WA

Post by Scarecrow » Sat Sep 01, 2012 8:21 pm

someone can help me plz? getting WA.

Code: Select all

AC
Do or do not. There is no try.

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 551 - Nesting a Bunch of Brackets

Post by metaphysis » 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"

Post Reply

Return to “Volume 5 (500-599)”