673 - Parentheses Balance
Moderator: Board moderators
673 Parentheses Balance
I don't understand the problem with my code.
Check it please:
[c]
#include<stdio.h>
main()
{
int i,j,cases,n_inside_stack;
char expression[200],stack[200],yes_or_no;
scanf("%d\n",&cases);
for(i=0;i<cases;i++)
{
yes_or_no=1;
gets(expression);
n_inside_stack=0;
for(j=0;j<strlen(expression);j++)
{
if(expression[j]=='('||expression[j]=='[')
stack[n_inside_stack++]=expression[j];
else if(expression[j]==')'||expression[j]==']')
{
if(n_inside_stack==0)
{
yes_or_no=0;
break;
}
else
{
n_inside_stack--;
if(stack[n_inside_stack]=='(')
{
if(expression[j]!=')')
{
yes_or_no=0;
break;
}
}
else
{
if(expression[j]!=']')
{
yes_or_no=0;
break;
}
}
}
}
}
if(yes_or_no==1)
printf("Yes\n");
else
printf("No\n");
}
}
[/c]
Check it please:
[c]
#include<stdio.h>
main()
{
int i,j,cases,n_inside_stack;
char expression[200],stack[200],yes_or_no;
scanf("%d\n",&cases);
for(i=0;i<cases;i++)
{
yes_or_no=1;
gets(expression);
n_inside_stack=0;
for(j=0;j<strlen(expression);j++)
{
if(expression[j]=='('||expression[j]=='[')
stack[n_inside_stack++]=expression[j];
else if(expression[j]==')'||expression[j]==']')
{
if(n_inside_stack==0)
{
yes_or_no=0;
break;
}
else
{
n_inside_stack--;
if(stack[n_inside_stack]=='(')
{
if(expression[j]!=')')
{
yes_or_no=0;
break;
}
}
else
{
if(expression[j]!=']')
{
yes_or_no=0;
break;
}
}
}
}
}
if(yes_or_no==1)
printf("Yes\n");
else
printf("No\n");
}
}
[/c]
Last edited by henar2 on Fri Jun 28, 2002 4:10 pm, edited 1 time in total.
check with input:
speed hint: for's end condition is evaluated in every cycle. don't use strlen() in it. speedup: 1.060 sec -> 0.120 sec.
Code: Select all
3
(
()(
[()
Last edited by Picard on Fri Jun 28, 2002 8:51 pm, edited 1 time in total.
Hi Picard, I have change the code to handle your input and to improve the speed but I continue be wrong answered.
Please teach me again
[c]
#include<stdio.h>
main()
{
int i,j,cases,n_inside_stack;
char expression[200],stack[200],yes_or_no,n;
scanf("%d\n",&cases);
for(i=0;i<cases;i++)
{
yes_or_no=1;
gets(expression);
n_inside_stack=0;
n=strlen(expression);
for(j=0;j<n;j++)
{
if(expression[j]=='('||expression[j]=='[')
stack[n_inside_stack++]=expression[j];
else if(expression[j]==')'||expression[j]==']')
{
if(n_inside_stack==0)
{
yes_or_no=0;
break;
}
else
{
n_inside_stack--;
if(stack[n_inside_stack]=='(')
{
if(expression[j]!=')')
{
yes_or_no=0;
break;
}
}
else
{
if(expression[j]!=']')
{
yes_or_no=0;
break;
}
}
}
}
}
if(yes_or_no==1 && n_inside_stack==0)
printf("Yes\n");
else
printf("No\n");
}
}
[/c]
Please teach me again
![:)](./images/smilies/icon_smile.gif)
[c]
#include<stdio.h>
main()
{
int i,j,cases,n_inside_stack;
char expression[200],stack[200],yes_or_no,n;
scanf("%d\n",&cases);
for(i=0;i<cases;i++)
{
yes_or_no=1;
gets(expression);
n_inside_stack=0;
n=strlen(expression);
for(j=0;j<n;j++)
{
if(expression[j]=='('||expression[j]=='[')
stack[n_inside_stack++]=expression[j];
else if(expression[j]==')'||expression[j]==']')
{
if(n_inside_stack==0)
{
yes_or_no=0;
break;
}
else
{
n_inside_stack--;
if(stack[n_inside_stack]=='(')
{
if(expression[j]!=')')
{
yes_or_no=0;
break;
}
}
else
{
if(expression[j]!=']')
{
yes_or_no=0;
break;
}
}
}
}
}
if(yes_or_no==1 && n_inside_stack==0)
printf("Yes\n");
else
printf("No\n");
}
}
[/c]
673: Parentheses Balance
I got Wrong Answer for 673
. Can anyone help me out??
[cpp]
void main () {
char input[1000], tempInput[1000];
char ch;
int len = 0;
int i,j,k;
i = j = k = 0;
int balanced = 1;
int numInput = 0;
cin >> numInput;
while(numInput>0){
cin>>input;
numInput--;
len = strlen(input);
strcpy(tempInput, input);
balanced = 1;
while(balanced){
for (i=0;i < len;i++) {
ch = tempInput;
if((ch==')') ||(ch==']')) break;
}
if ((i==0) || (i>=len)) {
balanced = 0;
}
else {
for (j=i-1;j>=0; j--) {
if ((ch==')') && (tempInput[j]=='(')) break;
else if ((ch==']') && (tempInput[j]=='[')) break;
else if ((ch==')') && (tempInput[j]=='[')) {
balanced = 0;
break;
}
else if ((ch==']') && (tempInput[j]=='(')) {
balanced = 0;
break;
}
}
if (j<0) {
balanced = 0;
break;
}
else if (balanced){
i++;
for (k=j; i<len; k++) {
tempInput[k] = tempInput[i++];
}
tempInput[k] = '\0';
len = k;
if (len<=0) break;
}
}
}
if (balanced)cout<<"Yes";
else cout<<"No";
cout<<endl;
}
}
/*"@END_OF_SOURCE_CODE"*/[/cpp]
![:(](./images/smilies/icon_frown.gif)
[cpp]
void main () {
char input[1000], tempInput[1000];
char ch;
int len = 0;
int i,j,k;
i = j = k = 0;
int balanced = 1;
int numInput = 0;
cin >> numInput;
while(numInput>0){
cin>>input;
numInput--;
len = strlen(input);
strcpy(tempInput, input);
balanced = 1;
while(balanced){
for (i=0;i < len;i++) {
ch = tempInput;
if((ch==')') ||(ch==']')) break;
}
if ((i==0) || (i>=len)) {
balanced = 0;
}
else {
for (j=i-1;j>=0; j--) {
if ((ch==')') && (tempInput[j]=='(')) break;
else if ((ch==']') && (tempInput[j]=='[')) break;
else if ((ch==')') && (tempInput[j]=='[')) {
balanced = 0;
break;
}
else if ((ch==']') && (tempInput[j]=='(')) {
balanced = 0;
break;
}
}
if (j<0) {
balanced = 0;
break;
}
else if (balanced){
i++;
for (k=j; i<len; k++) {
tempInput[k] = tempInput[i++];
}
tempInput[k] = '\0';
len = k;
if (len<=0) break;
}
}
}
if (balanced)cout<<"Yes";
else cout<<"No";
cout<<endl;
}
}
/*"@END_OF_SOURCE_CODE"*/[/cpp]
673
Why does this code get WA? Is anything I didn't consider yet?
[c]
#include<stdio.h>
#include<string.h>
#define YES 1
#define NO 0
void main(void)
{
int n,x,top,y,stack[130],error;
char s[130];
scanf("%d\n",&n);
for(x=0;x<n;x++)
{
gets(s);
if(!strlen(s))
{
printf("Yes\n");
continue;
}
for(y=0,top=0,error=NO;s[y]!='\0';y++)
if(s[y]=='(')
stack[top++]=1;
else if(s[y]=='[')
stack[top++]=2;
else
{
if(top && (s[y]==')' && stack[top-1]==1 || s[y]==']' && stack[top-1]==2))
top--;
else
{
error=YES;
break;
}
}
if(error)
printf("No\n");
else
printf("Yes\n");
}
}
[/c]
[c]
#include<stdio.h>
#include<string.h>
#define YES 1
#define NO 0
void main(void)
{
int n,x,top,y,stack[130],error;
char s[130];
scanf("%d\n",&n);
for(x=0;x<n;x++)
{
gets(s);
if(!strlen(s))
{
printf("Yes\n");
continue;
}
for(y=0,top=0,error=NO;s[y]!='\0';y++)
if(s[y]=='(')
stack[top++]=1;
else if(s[y]=='[')
stack[top++]=2;
else
{
if(top && (s[y]==')' && stack[top-1]==1 || s[y]==']' && stack[top-1]==2))
top--;
else
{
error=YES;
break;
}
}
if(error)
printf("No\n");
else
printf("Yes\n");
}
}
[/c]
I got the WA,too,but it runs very ok on my computer,and i really don't know what happened when it run 9n the judge system's computer!
i met the same problem in ACM 272,which i believe that my program can correctly solve it.
so i think there maybe some rules that i don't know when submit a problem?after all,i 'm a beginer!
[cpp]
#include <stdio.h>
#include <iostream.h>
class CStack
{
private:
char s[130];
int num;
public:
void clean()
{
num=0;
};
char isempty()
{
if (num==0)
return 1;
else
return 0;
};
char instack(char ch)
{
if ((ch=='(')||(ch=='['))
{
s[num]=ch;
num++;
return 1;
};
if (ch==')')
{
if ((num>0)&&(s[num-1]=='('))
{
num--;
return 1;
}
else
return 0;
}
if (ch==']')
{
if ((num>0)&&(s[num-1]=='['))
{
num--;
return 1;
}
else
return 0;
}
return 0;
};
};
void main()
{
int n,i;
CStack stack;
char ch,errorflag;
cin>>n;
for (i=1;i<=n;i++)
{
errorflag=0;
stack.clean();
ch=getchar();
while (ch!='\n')
{
if (stack.instack(ch)==0)
errorflag=1;
ch=getchar();
}
if ((stack.isempty()==1)&&(errorflag==0))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}[/cpp]
i'm eagerly hope that somebody is willing to give me a hand!
i met the same problem in ACM 272,which i believe that my program can correctly solve it.
so i think there maybe some rules that i don't know when submit a problem?after all,i 'm a beginer!
[cpp]
#include <stdio.h>
#include <iostream.h>
class CStack
{
private:
char s[130];
int num;
public:
void clean()
{
num=0;
};
char isempty()
{
if (num==0)
return 1;
else
return 0;
};
char instack(char ch)
{
if ((ch=='(')||(ch=='['))
{
s[num]=ch;
num++;
return 1;
};
if (ch==')')
{
if ((num>0)&&(s[num-1]=='('))
{
num--;
return 1;
}
else
return 0;
}
if (ch==']')
{
if ((num>0)&&(s[num-1]=='['))
{
num--;
return 1;
}
else
return 0;
}
return 0;
};
};
void main()
{
int n,i;
CStack stack;
char ch,errorflag;
cin>>n;
for (i=1;i<=n;i++)
{
errorflag=0;
stack.clean();
ch=getchar();
while (ch!='\n')
{
if (stack.instack(ch)==0)
errorflag=1;
ch=getchar();
}
if ((stack.isempty()==1)&&(errorflag==0))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}[/cpp]
i'm eagerly hope that somebody is willing to give me a hand!
673(wa)
Anyone can help me.
Why i got wa.
[cpp#include<stdio.h>
#include<string.h>
main()
{
int many=0,i=0,j=0,n=0,count=0;
char in[1000];
scanf("%d\n",&many);
while(many!=0)
{
gets(in);
n=strlen(in);
if(n%2==0)
{
i=0;
while(i<n)
{
if(in!='0')
{
j=i+1;
while(in[j]=='0')
j++;
if(in=='('&&in[j]==')')
{
count++;
in='0';
in[j]='0';
i=0;
}
else if(in=='['&&in[j]==']')
{
count++;
in='0';
in[j]='0';
i=0;
}
else
i++;
}
else
i++;
}
many--;
if(n/2==count)
printf("Yes\n");
else
printf("No\n");
n=strlen(in);
for(i=0;i<n;i++)
in=='\0';
count=0;
} else
printf("No\n");
}
}[/cpp]
Why i got wa.
[cpp#include<stdio.h>
#include<string.h>
main()
{
int many=0,i=0,j=0,n=0,count=0;
char in[1000];
scanf("%d\n",&many);
while(many!=0)
{
gets(in);
n=strlen(in);
if(n%2==0)
{
i=0;
while(i<n)
{
if(in!='0')
{
j=i+1;
while(in[j]=='0')
j++;
if(in=='('&&in[j]==')')
{
count++;
in='0';
in[j]='0';
i=0;
}
else if(in=='['&&in[j]==']')
{
count++;
in='0';
in[j]='0';
i=0;
}
else
i++;
}
else
i++;
}
many--;
if(n/2==count)
printf("Yes\n");
else
printf("No\n");
n=strlen(in);
for(i=0;i<n;i++)
in=='\0';
count=0;
} else
printf("No\n");
}
}[/cpp]
Last edited by lendlice on Tue Apr 01, 2003 4:17 pm, edited 1 time in total.
-
- New poster
- Posts: 39
- Joined: Wed Jan 22, 2003 11:02 am
I also WA in this Question. I am using stack to do this.Please help me to take a look.
[cpp]
#include <iostream.h>
#include <stdio.h>
class s{
public:
char stack[1000];
char pop(void);
int push(char);
};
s array;
int times,i;
char tempchar;
int check(void);
int right1;
char get;
int arrayto,to;
char dummy;
char p[200];
void main(void)
{
cin>>times;
arrayto=-1;
for (i=0;i<times;i++)
{
gets(p);
arrayto=-1;to=-1;
while (1)
{
to++;
tempchar=p[to];
if (tempchar=='\0')
{
right1=check();
if (right1==1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
break;
}
if (tempchar=='(')
array.push('(');
if (tempchar=='[')
array.push ('[');
if (tempchar==')')
{
get=array.pop();
if (get!='(')
{
cout<<"No"<<endl;
break;
}
}
if (tempchar==']')
{
get=array.pop ();
if (get!='[')
{
cout<<"No"<<endl;
break;
}
}
}
}
}
char s::pop(void)
{
char re;
if (arrayto==-1)
return 'E';
re=array.stack[arrayto];
arrayto--;
return re;
}
int s::push (char get)
{
arrayto++;
array.stack[arrayto]=get;
return 0;
}
int check(void)
{
int i,j,k;
if (arrayto!=-1)
return 0;
else
return 1;
}
[/cpp]
[cpp]
#include <iostream.h>
#include <stdio.h>
class s{
public:
char stack[1000];
char pop(void);
int push(char);
};
s array;
int times,i;
char tempchar;
int check(void);
int right1;
char get;
int arrayto,to;
char dummy;
char p[200];
void main(void)
{
cin>>times;
arrayto=-1;
for (i=0;i<times;i++)
{
gets(p);
arrayto=-1;to=-1;
while (1)
{
to++;
tempchar=p[to];
if (tempchar=='\0')
{
right1=check();
if (right1==1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
break;
}
if (tempchar=='(')
array.push('(');
if (tempchar=='[')
array.push ('[');
if (tempchar==')')
{
get=array.pop();
if (get!='(')
{
cout<<"No"<<endl;
break;
}
}
if (tempchar==']')
{
get=array.pop ();
if (get!='[')
{
cout<<"No"<<endl;
break;
}
}
}
}
}
char s::pop(void)
{
char re;
if (arrayto==-1)
return 'E';
re=array.stack[arrayto];
arrayto--;
return re;
}
int s::push (char get)
{
arrayto++;
array.stack[arrayto]=get;
return 0;
}
int check(void)
{
int i,j,k;
if (arrayto!=-1)
return 0;
else
return 1;
}
[/cpp]
So far as I understand, you are not handling the input properly. I haven't compiled your code, but it seems that after reading the integer (number of test cases) the file pointer would remain on that line. Thus your first gets call will only bring the file pointer to the next line.
I think your program should fail in the following test case:
Your program should give the output:
Whereas the correct output is:
I think your program should fail in the following test case:
Code: Select all
3
)
()
)(
Code: Select all
Yes
No
Yes
Code: Select all
No
Yes
No
K M Hasan
http://www.cs.umanitoba.ca/~kmhasan/
http://www.cs.umanitoba.ca/~kmhasan/
-
- New poster
- Posts: 39
- Joined: Wed Jan 22, 2003 11:02 am