673 - Parentheses Balance

[henar2]

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]

[Picard]

check with input:

Code: Select all

3
(
()(
[()

speed hint: for's end condition is evaluated in every cycle. don't use strlen() in it. speedup: 1.060 sec -> 0.120 sec.

[henar2]

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]

[10153EN]

I think there's a small mistake, you declare n to be char, which will have value overflow when n > 127.

[henar2]

Thank you.

I didn't realize the char declaration.
Accepted.

[knapsack]

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]

[htl]

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]

[jiangwen]

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!

[deddy one]

check with the input :

([)]

it should be:

No

Btw, are you sure cin and cout handle the input correctly??
I'm using gets on this one

[lendlice]

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]

[shamim]

I think you should use stack to store which closing Parantheses is the next valid one.

[Partha]

Your code is a bit complecated. Try to use 'stack' to solve this problem. In this method i got AC.

[SilVer DirectXer]

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]

[kmhasan]

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:

Code: Select all

3
)
()
)(

Your program should give the output:

Code: Select all

Yes
No
Yes

Whereas the correct output is:

Code: Select all

No
Yes
No

[SilVer DirectXer]

thanks for yr help....
but..
the case that u mentioned..i could handle correctly..

anyways, thanks for yr help..