551 - Nesting a Bunch of Brackets

[Emilio]

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]

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]

"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]

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.

[Raj Ariyan]

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.

[CodeMaker]

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

[Raj Ariyan]

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

[lpereira]

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]

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]

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

[Ndiyaa ndako]

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]

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]

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]

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]

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.