673 - Parentheses Balance

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Location: Valladolid (Spain)

673 Parentheses Balance

Post by henar2 » Fri Jun 28, 2002 1:42 pm

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]
Last edited by henar2 on Fri Jun 28, 2002 4:10 pm, edited 1 time in total.

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post by Picard » Fri Jun 28, 2002 1:57 pm

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.
Last edited by Picard on Fri Jun 28, 2002 8:51 pm, edited 1 time in total.

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Location: Valladolid (Spain)

Post by henar2 » Fri Jun 28, 2002 5:52 pm

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
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN » Fri Jun 28, 2002 7:43 pm

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

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Location: Valladolid (Spain)

Post by henar2 » Fri Jun 28, 2002 9:19 pm

Thank you.
:D
I didn't realize the char declaration.
Accepted.

knapsack
New poster
Posts: 3
Joined: Tue Jun 25, 2002 8:12 pm

673: Parentheses Balance

Post by knapsack » Sat Jul 20, 2002 1:24 am

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
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

673

Post by htl » Thu Aug 15, 2002 5:25 pm

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
New poster
Posts: 2
Joined: Sat Oct 05, 2002 3:03 am

Post by jiangwen » Sat Oct 12, 2002 6:24 pm

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
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Sat Dec 21, 2002 11:26 am

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
New poster
Posts: 22
Joined: Thu Nov 21, 2002 10:50 am

673(wa)

Post by lendlice » Sun Mar 30, 2003 5:21 am

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]
Last edited by lendlice on Tue Apr 01, 2003 4:17 pm, edited 1 time in total.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sun Mar 30, 2003 2:17 pm

I think you should use stack to store which closing Parantheses is the next valid one.
Last edited by shamim on Wed Apr 09, 2003 7:19 am, edited 1 time in total.

Partha
New poster
Posts: 5
Joined: Fri Mar 28, 2003 8:51 pm
Location: Bangladesh
Contact:

Post by Partha » Tue Apr 08, 2003 5:35 pm

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

SilVer DirectXer
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

Post by SilVer DirectXer » Sat Apr 12, 2003 8:51 pm

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]

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan » Sun Apr 13, 2003 4:41 am

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
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

Post by SilVer DirectXer » Sun Apr 13, 2003 4:34 pm

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

anyways, thanks for yr help..

Post Reply

Return to “Volume 6 (600-699)”