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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

551 - Nesting a Bunch of Brackets

Post by Adrian Kuegel » Wed Mar 20, 2002 7:04 pm

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
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn » Wed Mar 20, 2002 7:47 pm

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Mar 21, 2002 6:23 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Mar 21, 2002 6:30 pm

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
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Thu Mar 21, 2002 7:18 pm

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
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

Why WA?

Post by xenon » Sun Jul 07, 2002 12:52 pm

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...
Last edited by xenon on Sun Jul 07, 2002 2:52 pm, edited 1 time in total.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Sun Jul 07, 2002 2:11 pm

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

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

Post by xenon » Sun Jul 07, 2002 3:17 pm

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

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Sun Jul 07, 2002 3:42 pm

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

Ivor

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

551 help

Post by obayashi » Sun Aug 11, 2002 6:09 am

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]
Time makes a fool of memory
And yet my memories still shine

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

Post by obayashi » Sun Aug 11, 2002 6:44 am

and what about such cases below?

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

my program gives
NO 3
NO 1
NO 3
NO 3

...
Time makes a fool of memory
And yet my memories still shine

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

Post by obayashi » Sun Aug 11, 2002 6:57 am

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

...
Time makes a fool of memory
And yet my memories still shine

off_algos
New poster
Posts: 29
Joined: Wed Nov 13, 2002 11:37 am
Location: india

still WA

Post by off_algos » Tue Dec 17, 2002 3:07 pm

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

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Fri Aug 22, 2003 4:38 am

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

Mahmud776
New poster
Posts: 22
Joined: Mon Dec 22, 2003 9:29 am
Location: Canada

551

Post by Mahmud776 » Wed Jan 21, 2004 8:29 pm

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

Post Reply

Return to “Volume 5 (500-599)”