Page 1 of 4

551 - Nesting a Bunch of Brackets

Posted: Wed Mar 20, 2002 7:04 pm
by 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.

Posted: Wed Mar 20, 2002 7:47 pm
by LittleJohn
(**()**)+ -> YES
(**> -> NO 3
* -> YES
[]<> -> YES
and my output for a blank line is YES.

Posted: Thu Mar 21, 2002 6:23 pm
by 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?

Posted: Thu Mar 21, 2002 6:30 pm
by 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?

Posted: Thu Mar 21, 2002 7:18 pm
by 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>

Why WA?

Posted: Sun Jul 07, 2002 12:52 pm
by 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...

Posted: Sun Jul 07, 2002 2:11 pm
by Caesum
Maybe:
[
Mine gives:
NO 2
Your program gives:
NO 1

Posted: Sun Jul 07, 2002 3:17 pm
by 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 :D

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

Posted: Sun Jul 07, 2002 3:42 pm
by Ivor
First offending bracket is not '['. Actually the 'offending bracket' in your case is '\n'.

Ivor

551 help

Posted: Sun Aug 11, 2002 6:09 am
by 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]

Posted: Sun Aug 11, 2002 6:44 am
by obayashi
and what about such cases below?

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

my program gives
NO 3
NO 1
NO 3
NO 3

...

Posted: Sun Aug 11, 2002 6:57 am
by 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...
obayashi wrote: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

...

still WA

Posted: Tue Dec 17, 2002 3:07 pm
by 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

Posted: Fri Aug 22, 2003 4:38 am
by UFP2161
obayashi wrote: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).

551

Posted: Wed Jan 21, 2004 8:29 pm
by 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