551 - Nesting a Bunch of Brackets
Moderator: Board moderators
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
551 - Nesting a Bunch of Brackets
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.
(**()**)+
(**>
*
[]<>
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.
-
- Learning poster
- Posts: 83
- Joined: Wed Feb 27, 2002 2:00 am
- Location: Taiwan
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
How about
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>
Code: Select all
(*(*))
((*)
([)]
([ ])()(**)
*)
[
(
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?
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...
[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.
Thanks Caesum, that was it. Got accepted now.
One thing bothers me, though: The description says:
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:
Gives (mind the spaces at the end of the lines!):
Happy hunting!
-xenon
One thing bothers me, though: The description says:
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.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.
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](./images/smilies/icon_biggrin.gif)
Also this makes the answers given earlier in this thread incorrect.
For everybody struggling with this problem:
Code: Select all
(*a++(*)
(*a{+}*)
(*(*))
((*)
([)]
([ ])()(**)
*)
[
(
[
Code: Select all
NO 6
YES
NO 3
NO 3
NO 3
YES
NO 1
NO 3
NO 11
NO 2
-xenon
551 help
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]
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
And yet my memories still shine
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...
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
And yet my memories still shine
still WA
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]
help me
551
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
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