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

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Mon May 30, 2005 9:58 pm

Hi!
When the answer is "No" you must print the number of chars+1, (remember that (* and *) is only a char), I think that one of yours faults is that you counter [* and *] as one char but only (* and *) are one char.

Hope it help!

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Mon May 30, 2005 11:26 pm

No, I do not count [* and/or *] as one char.

I should have some other problem which I currently
can not exactly find out what could be.

Do you know some Java, I can send you my code
although I haven't done this so far.

What do you mean by "you must print the number of chars+1" ?!

Problem says this:

Code: Select all

If the expression is not properly nested your program should determine the position of the offending bracket, that is the length of the shortest prefix of the expression that can not be extended to a properly nested expression
This contradicts almost all ACC outputs I've found in threads
here, apparently the Judge's tests do not follow this logic.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Tue May 31, 2005 9:48 pm

"you must print the number of chars+1" ?!
I only refer to the examples that you have posted.
If the expression is not properly nested your program should determine the position of the offending bracket, that is the length of the shortest prefix of the expression that can not be extended to a properly nested expression
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

if you want can send me your code.

Good luck!

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Sat Jun 04, 2005 5:10 pm

The outputs given by jagadish is very helpful.

The first output for : (*adf(y)(* given NO 9 by jagadish is ok.

for (* no missmatch count=1;
for a no missmatch count=2;
for d no missmatch count=3;
for f no missmatch count=4;
for ( no missmatch count=5;
for y no missmatch count=6;
for ) no missmatch count=7;
for (* no missmatch count=8;

string is complete but still all the brackets are not closed, so a missmatch occured and the error must go in the empty place, because till count=8 everything is ok, so no complain, thats why error is in the 8+1=9th place, so answer is "NO 9"

I hope it helps. :)
Last edited by CodeMaker on Tue Jun 07, 2005 2:00 pm, edited 1 time in total.
Jalal : AIUB SPARKS

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

!!!!!

Post by Raj Ariyan » Sun Jun 05, 2005 6:52 pm

Hi CodeMaker,
I'm still little bit confuced, what u'r talking abt 11th and 13th Case ???
Jagadish has been sent his output by his ACC solution. I think there is no this type of input in the judge.
Say from u'r opinion <>< should be YES, but if so then why not
(*adf(y)( is Correct. It can also be valid by adding *)). And one think for blank line output should be YES, right ??? My code passed all output with Jagadish Output, but still wrong answer. Anyone plz help me.
Some Love Stories Live Forever ....

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Tue Jun 07, 2005 1:58 pm

:oops: Hi , sorry jagadish's output is ok, somehow I missed the angular brackets and still got acc thats because I/O data has no missmatch case for the angular brackets, i m really sorry about that. for blank line my code prints Yes.

I modified my code now, here is some I/O from my code, u can check.

Code: Select all

Input:

( ( ( ( ) ( ) ) ) )
<<<<
{{{>>>
()()()()()
<><><><>
{}{}{}{}
AAAA{}BBBBB
AAAA{]BBBBB
*()*
<***>
#!^$!^<><>{[<[}]>
<11323   >*(

BLANK BEFORE
(*)(*)*()*(**)

output:

YES
NO 5
NO 4
YES
YES
YES
YES
NO 6
YES
YES
NO 15
NO 13
YES
YES
NO 2


Jalal : AIUB SPARKS

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

Hi

Post by Raj Ariyan » Wed Jun 08, 2005 7:23 pm

Hi CodeMaker,
Thanx for your reply. I solved it yesterday. I dont know if u ignore <> then how ur code got accept ? It seems that there is no judge data like that. Very Confusing !!! :roll: :roll: :roll:
Some Love Stories Live Forever ....

lpereira
New poster
Posts: 5
Joined: Wed Nov 16, 2005 7:35 pm
Location: Campinas - SP - Brazil
Contact:

Some help

Post by lpereira » Fri May 05, 2006 8:34 pm

My AC code gives, for this input:

Code: Select all

((**)()a+b)[(a){a+n}]
((**)()a+b)[(a){a+n}](*
((**)()a+b)[(a){a+n}](
((**)()a+b)[(a){a+n}])
(((**))()a+b)[(a){a+n}]
[((((**))())a+b)][[(a){a+n}]]
[((((**))())a+b)][[(a){a+n}]]u+i-9+(+=
()a
a()
()*
()*()
()()(a+b)(
[**
((((())
(*(*(*(**)*)
(
 (
  (
   (
(*)
**()**(**)

(note: the last line is an actual blank line. It was processed)

this output

Code: Select all

YES
NO 21
NO 21
NO 20
YES
YES
NO 37
YES
YES
YES
YES
NO 11
NO 4
NO 8
NO 7
NO 2
NO 3
NO 4
NO 5
NO 2
YES
YES

rcrezende
New poster
Posts: 7
Joined: Mon Nov 28, 2005 4:53 am

Post by rcrezende » Sat May 06, 2006 1:56 am

I have submitted this code and was judged as WA. I dont know the problem, cause I tested a lot of inputs from eletronic board and the output is always the same.
Below is the code, an input and output.
Please, I need some help!!!

Code: Select all

Source removed, ACCEPTED
Input:

Code: Select all

(
)
(*
*)
{dummy}
*()*
(*)
(* < *) > *)
(* <> *) > *)
rodrigo
**(
()a
a()
()*
()*() 
((**)()a+b)[(a){a+n}]
((**)()a+b)[(a){a+n}](*
((**)()a+b)[(a){a+n}](
((**)()a+b)[(a){a+n}])
(((**))()a+b)[(a){a+n}]
[((((**))())a+b)][[(a){a+n}]]
[((((**))())a+b)][[(a){a+n}]]u+i-9+(+=
()a
a()
()*
()*()
()()(a+b)(
[**
((((())
(*(*(*(**)*)
(*)
**()**(**)
(*adf(y)(*
(*adf(y)(
(a*)
)()
*)()
ads()asdf
(***)
(**
({{]}]
(**){*{]}]
<><
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)>
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)><
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)>(*
[**
((((())
(*(*(*(**)*)
(**********(
(*a++(*)
(*a{+}*)
(*)
(**)
((**))
((()))
{}{}{}{}{}{}{}{}{
{{{}[()((**))][][]}}
(())))
(***)
{*(())(()*)*}
{adfadf[adfadf(adfa(*adfadf*)adfaf)(*afdsf*)]adfadf}
(AADFASDFADSF)
(**
[**
((((())
(*(*(*(**)*)
(*adf(y)(*
( ( ( ( ) ( ) ) ) )
<<<<
{{{>>>
()()()()()
<><><><>
{}{}{}{}
AAAA{}BBBBB
AAAA{]BBBBB
*()*
<***>
#!^$!^<><>{[<[}]>
<11323   >*(

BLANK BEFORE
(*)(*)*()*(**) 
My WA output

Code: Select all

NO 2
NO 1
NO 2
NO 1
YES
YES
NO 2
NO 5
NO 8
YES
NO 4
YES
YES
YES
YES
YES
NO 21
NO 21
NO 20
YES
YES
NO 37
YES
YES
YES
YES
NO 11
NO 4
NO 8
NO 7
NO 2
YES
NO 9
NO 9
NO 3
NO 1
NO 1
YES
YES
NO 3
NO 4
NO 6
NO 4
YES
NO 37
NO 37
NO 4
NO 8
NO 7
NO 12
NO 6
YES
NO 2
YES
YES
YES
NO 18
YES
NO 5
YES
NO 10
YES
YES
NO 3
NO 4
NO 8
NO 7
NO 9
YES
NO 5
NO 4
YES
YES
YES
YES
NO 6
YES
YES
NO 15
NO 13
YES
YES
NO 2
[/code]

rcrezende
New poster
Posts: 7
Joined: Mon Nov 28, 2005 4:53 am

Some Help

Post by rcrezende » Sat May 06, 2006 1:58 am

I have submitted this code and was judged as WA. I dont know the problem, cause I tested a lot of inputs from eletronic board and the output is always the same.
Below is the code, an input and output.
Please, I need some help!!!

Code: Select all

code removed, ACCEPTED
Input:

Code: Select all

(
)
(*
*)
{dummy}
*()*
(*)
(* < *) > *)
(* <> *) > *)
rodrigo
**(
()a
a()
()*
()*() 
((**)()a+b)[(a){a+n}]
((**)()a+b)[(a){a+n}](*
((**)()a+b)[(a){a+n}](
((**)()a+b)[(a){a+n}])
(((**))()a+b)[(a){a+n}]
[((((**))())a+b)][[(a){a+n}]]
[((((**))())a+b)][[(a){a+n}]]u+i-9+(+=
()a
a()
()*
()*()
()()(a+b)(
[**
((((())
(*(*(*(**)*)
(*)
**()**(**)
(*adf(y)(*
(*adf(y)(
(a*)
)()
*)()
ads()asdf
(***)
(**
({{]}]
(**){*{]}]
<><
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)>
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)><
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)>(*
[**
((((())
(*(*(*(**)*)
(**********(
(*a++(*)
(*a{+}*)
(*)
(**)
((**))
((()))
{}{}{}{}{}{}{}{}{
{{{}[()((**))][][]}}
(())))
(***)
{*(())(()*)*}
{adfadf[adfadf(adfa(*adfadf*)adfaf)(*afdsf*)]adfadf}
(AADFASDFADSF)
(**
[**
((((())
(*(*(*(**)*)
(*adf(y)(*
( ( ( ( ) ( ) ) ) )
<<<<
{{{>>>
()()()()()
<><><><>
{}{}{}{}
AAAA{}BBBBB
AAAA{]BBBBB
*()*
<***>
#!^$!^<><>{[<[}]>
<11323   >*(

BLANK BEFORE
(*)(*)*()*(**) 
My WA output

Code: Select all

NO 2
NO 1
NO 2
NO 1
YES
YES
NO 2
NO 5
NO 8
YES
NO 4
YES
YES
YES
YES
YES
NO 21
NO 21
NO 20
YES
YES
NO 37
YES
YES
YES
YES
NO 11
NO 4
NO 8
NO 7
NO 2
YES
NO 9
NO 9
NO 3
NO 1
NO 1
YES
YES
NO 3
NO 4
NO 6
NO 4
YES
NO 37
NO 37
NO 4
NO 8
NO 7
NO 12
NO 6
YES
NO 2
YES
YES
YES
NO 18
YES
NO 5
YES
NO 10
YES
YES
NO 3
NO 4
NO 8
NO 7
NO 9
YES
NO 5
NO 4
YES
YES
YES
YES
NO 6
YES
YES
NO 15
NO 13
YES
YES
NO 2

User avatar
Ndiyaa ndako
New poster
Posts: 21
Joined: Sat Sep 25, 2004 3:35 am
Location: Oaxaca de Ju
Contact:

Hint

Post by Ndiyaa ndako » Sun Jun 11, 2006 4:35 am

If there is an unmatched closing bracket, output the position of the first one with this property. Otherwise, output the length of expression plus one.

rcrezende
New poster
Posts: 7
Joined: Mon Nov 28, 2005 4:53 am

Post by rcrezende » Sun Jun 11, 2006 4:46 am

My program had WA because it was used a char variable to manage the string's position. I changed to integer and got ACCEPT!!!
This output above is CORRECT!!!!

karu
New poster
Posts: 5
Joined: Tue Jun 13, 2006 5:31 am
Location: New Zealand
Contact:

Post by karu » Thu Jun 29, 2006 9:49 am

The problem description is completely wrong.

"In this problem we consider expressions containing brackets that are properly nested. These expressions are obtained by juxtaposition of properly netsted expressions in a pair of matching brackets, the left one an opening and the right one a closing bracket."

There are many problems with this; I will describe one of them.

From "These [properly nested] expressions are obtained by juxtaposition of properly netsted expressions in a pair of matching brackets", we can see that every properly nested expression contains a juxtaposition of properly nested expressions. Therefore, a properly nested expression can never be empty (since this is not a juxtaposition). We can therefore conclude that every properly nested expression must be infinite in size.

Am I wrong?

koalahong
New poster
Posts: 2
Joined: Sun Jul 09, 2006 8:01 pm

551 Nesting a Bunch of Brackets WA

Post by koalahong » Sun Jul 09, 2006 11:02 pm

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;
}

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

Please someone give me the output of the test cases below

Post by arif_pasha » Sun Feb 25, 2007 11:12 pm

Can anyone AC'er give me the output for the following test cases:

Code: Select all

()(***)(**)
()(***)(*)
({{}{}}[{(){}[]}
([))
()(**)
()*
aaaaaaa
aaa(aaaa
*******
a*a*a*a
()a
a()
()*()
(*a{+}*)
**)
*(*
(*a++(*)

Thanks in advance.

Post Reply

Return to “Volume 5 (500-599)”