551 - Nesting a Bunch of Brackets

[Adrian Kuegel]

Can someone please help me and give me the correct output for this input:
(**()**)+
(**>
*
[]<>
I don't know why I get always Wrong Answer. My output is:
NO 7
NO 3
NO 1
NO 3
And what is the output for blank line?
I have tried both YES and NO 1.

[LittleJohn]

(**()**)+ -> YES
(**> -> NO 3
* -> YES
[]<> -> YES
and my output for a blank line is YES.

[Adrian Kuegel]

Thank you for your reply. I have misunderstood the description and thought, that a properly nested expression must be included in brackets. But i'm still getting wrong answer. Is there another thing to think of?

[Adrian Kuegel]

Thank you for your reply. I have misunderstood the description and thought, that a properly nested expression must be included in brackets. But i'm still getting wrong answer. Is there another thing to think of?

[Ivor]

How about

Code: Select all

(*(*))
((*)
([)]
([  ])()(**)
*)
[
     (   

Output:
NO 3
NO 3
NO 3
YES
NO 1
NO 2
NO 10
/* (it contains spaces at the beginning and at the end) */

Ivor


<font size=-1>[ This Message was edited by: Ivor on 2002-03-21 18:18 ]</font>

<font size=-1>[ This Message was edited by: Ivor on 2002-03-21 18:19 ]</font>

[xenon]

My program gives the right answers for the examples in this thread, and FAIK it is correct. Could someone point me to the fault?

[pascal]
program p551(input,output);

{[(<(* SPOILER DELETED *)>)]}

[/pascal]


One thing I noticed, is that there are no Pascal programs in the problems stats, but I can see no reason why Pascal would give a different solution then C, C++ or JAVA.

Note: In standard Pascal the order in which expressions in a boolean evaluation are processed is undefined, so I write
[pascal]if (lineptr<linelength) then if (line[lineptr+1]=')') then [/pascal]
instead of
[pascal]if ((lineptr<linelength) and (line[lineptr+1]=')')) then [/pascal]
allthough I know both my compiler and the Judge's will give the same answer in both cases. This also accounts for the somewhat silly looking contstruction for handling a '('-character.
That's life...

[Caesum]

Maybe:
[
Mine gives:
NO 2
Your program gives:
NO 1

[xenon]

Thanks Caesum, that was it. Got accepted now.

One thing bothers me, though: The description says:

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.

I'm not too shure what it means (is it my English, or is it vague). The 'offending bracket' in the expression "[" would be the '[', but in the expression "[)" it would be the ')'. The answer in both cases should be "NO 2" (according to the judge), although this would, in the first case, refer to the virtual bracket past the end of the line.
The second half of the quote talks about the 'prefix of the expression', which, in Dutch at least, can never be part of the expression itself. It makes no sense to me, however often I read it. So please enlighten me

Also this makes the answers given earlier in this thread incorrect.
For everybody struggling with this problem:

Code: Select all

(*a++(*)
(*a{+}*)
(*(*)) 
((*) 
([)] 
([  ])()(**) 
*) 
[ 
     (    
[

Gives (mind the spaces at the end of the lines!):

Code: Select all

NO 6
YES
NO 3
NO 3
NO 3
YES
NO 1
NO 3
NO 11
NO 2

Happy hunting!
-xenon

[Ivor]

First offending bracket is not '['. Actually the 'offending bracket' in your case is '\n'.

Ivor

[obayashi]

I've thought about possible test cases but still got WA:(
here's my code
any one help pls~

[cpp]
#include <iostream>
#include <stack>
#include <string.h>
using namespace std;
char str[10000];
int solve () {
int count,idx,len;
stack<int> st;
count = 0;
idx = 0;
len = strlen(str);
st.push(0);
while (idx<len) {
count++;
switch (str[idx]) {
case '(':
if (str[idx+1]=='*') {
idx++;
st.push(5);
} else {
st.push(1);
}
break;
case '[':
st.push(2);
break;
case '{':
st.push(3);
break;
case '<':
st.push(4);
break;
case '*':
if (idx==0) return 1;
if (st.size()==1) return count;
if (str[idx+1]==')') {
if (st.top()!=5) {
return count;
} else {
idx++;
st.pop();
}
}
break;
case ')':
if (st.top()!=1)
return count;
else
st.pop();
break;
case ']':
if (st.top()!=2)
return count;
else
st.pop();
break;
case '}':
if (st.top()!=3)
return count;
else
st.pop();
break;
case '>':
if (st.top()!=4)
return count;
else
st.pop();
break;
default:
if (idx==0) return 1;
if (st.size()==1) return count;
break;
}
idx++;
}
if (st.size()!=1) return count+1;
return 0;
}
int main () {
int r;
cin.getline(str,9999);
while (str[0]!='\0') {
r = solve();
if (r)
cout<<"NO "<<r<<endl;
else
cout<<"YES"<<endl;
cin.getline(str,9999);
}
return 0;
}
[/cpp]

[obayashi]

and what about such cases below?

()a
a()
()*
()*()

my program gives
NO 3
NO 1
NO 3
NO 3

...

[obayashi]

i've modified the code and then got AC
but there're still some questions...

i think the cases above should require "NO" instead of "YES" 'coz the charactors are not actually bracketed in pairs of brackets...

and what about such cases below?

()a
a()
()*
()*() <--- it seems that "*" is bracketed, but actually NOT...

my program gives
NO 3
NO 1
NO 3
NO 3

...

[off_algos]

Code: Select all

[cpp]
#include <stdio.h>

char stack[1000];
int top;
void push(char a)
{
    stack[top++]=a;
    if(top==1000)
	while(1);
}
char pop(void)
{
    if(top<0)
	return -1;
    else
	return stack[--top];
}
int main()
{
    int pos;
    char a[3000];
    int flag;
    while(gets(a))
    {
	top=0;
	pos=0;
	flag=0;
	int i=0;
	while(a[i])
	{
	    switch(a[i++])
	    {
	    case '(':
		if(a[i]=='*')
		{
		    push('*');
		    i++;
		}
		else
		    push('(');
		pos++;
		break;
	    case '<':
		push('<');
		pos++;
		break;
	    case '[':
		push('[');
		pos++;
		break;
	    case '{':
		push('{');
		pos++;
	    case '*':
		pos++;
		if(a[i]==')')
		{
		    i++;
		    if(pop()!='*')
		    {
			printf("NO %d\n",pos);		
			flag=1;
		    }
		}
		else
		{
		    goto default1;
		}
		break;
	    case ')':
		pos++;
		if(pop()!='(')
		{
		    printf("NO %d\n",pos);
		    flag=1;
		}
		break;
	    case '}':
		pos++;
		if(pop()!='{')
		{
		    printf("NO %d\n",pos);
		    flag=1;
		}
		break;
	    case '>':
		pos++;
		if(pop()!='<')
		{
		    printf("NO %d\n",pos);
		    flag=1;
		}
		break;
	    case ']':
		pos++;
		if(pop()!='[')
		{
		    printf("NO %d\n",pos);
		    flag=1;
		}
		break;
	    default:
		pos++;
	    default1:
		if(top<=0)
		{
		    printf("NO %d\n",pos);
		    flag=1;
		}
	    }
	    if(flag)
		break;
	}
	if(flag!=1)
	{
	    if(top==0)
		printf("YES\n");
	    else
		printf("NO %d\n",pos);
	}
    }
    return 0;
}
[/cpp]

well is still am confused as to why i get a wrong answer.
help me

[UFP2161]

i think the cases above should require "NO" instead of "YES" 'coz the characters are not actually bracketed in pairs of brackets...

No, the characters need not be inside any brackets (think of any standard mathematical statement, numbers can be inside or outside parentheses).

[Mahmud776]

Here I gave some inputs and it's outputs
Inputs:
((**)()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()
()*
()*()

Outputs:
YES
NO 21
NO 20
NO 20
YES
YES
NO 37
YES
YES
YES
YES
YES