## 551 - Nesting a Bunch of Brackets

Moderator: Board moderators

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
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!

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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
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
"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!

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm

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

### !!!!!

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 ....

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
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

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 !!!
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

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
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.

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)(
[**
((((())
(*(*(*(**)*)
(*)
**()**(**)
(a*)
)()
*)()
(***)
(**
({{]}]
(**){*{]}]
<><
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)>
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)><
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)>(*
[**
((((())
(*(*(*(**)*)
(**********(
(*a++(*)
(*a{+}*)
(*)
(**)
((**))
((()))
{}{}{}{}{}{}{}{}{
{{{}[()((**))][][]}}
(())))
(***)
{*(())(()*)*}
(**
[**
((((())
(*(*(*(**)*)
( ( ( ( ) ( ) ) ) )
<<<<
{{{>>>
()()()()()
<><><><>
{}{}{}{}
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

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.

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)(
[**
((((())
(*(*(*(**)*)
(*)
**()**(**)
(a*)
)()
*)()
(***)
(**
({{]}]
(**){*{]}]
<><
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)>
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)><
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)>(*
[**
((((())
(*(*(*(**)*)
(**********(
(*a++(*)
(*a{+}*)
(*)
(**)
((**))
((()))
{}{}{}{}{}{}{}{}{
{{{}[()((**))][][]}}
(())))
(***)
{*(())(()*)*}
(**
[**
((((())
(*(*(*(**)*)
( ( ( ( ) ( ) ) ) )
<<<<
{{{>>>
()()()()()
<><><><>
{}{}{}{}
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

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

### Hint

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
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:
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

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
Contact:

### Please someone give me the output of the test cases below

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++(*)