673 - Parentheses Balance

[komisarskip]

i can't find mistake in output

[I LIKE GN]

hello all.
i get WA...
here is my code

Code: Select all

#include <stdio.h>
char flag, formed, line[130];
int count;

void read(char prev, char *t, char X){
	if( flag )return ;
	char s, x = true;
	s = X? X: line[count++];

	if( (s=='\r' || s == -1) && prev == -1 ){formed = 1; return;}

	if( s == ')' && prev !='(' || s==']' && prev!='[' ){
		flag = true;
		return ;
	}
	if( s == ')' || s==']' ){
		*t = false;
		return;
	}
	if(s=='\r'){
		formed = flag = true;
		return;
	}
	read(s, &x, 0);
	if(x && flag==0){
		s = line[count++];
		/* it must be closing sequence */
		if(s=='\r'){
			formed = flag = true;
			return;
		}
		while( s == '(' || s == '[' ){
			read(prev,&x, s);
			s = line[count++];
		}
	}
}

void main(void){
	//freopen("i:\\a\\673.txt","rb",stdin);

	int cas; char t;

	scanf("%d", &cas); t = getchar(); t = getchar();
	while( cas--) {
		gets( line );
		if( line[0] == 13 ){
			puts("Yes");
		}
		else{
			count = 0;
			flag = formed = false; t = -1;
			while( !formed && !flag ){
				read(-1, &t, 0);
			}
			flag?puts("No"):puts("Yes");
		}
	}
}

i amm used recursive.
thx in advance...

[LPH]

Code: Select all

	scanf("%d", &cas); t = getchar(); t = getchar();

I didn't look through your recursive body, but this might be the problem of your code. A newline in Un*x is represented only by a character '\n', but in Windows, it's represented by '\r' '\n'. Thus when your program runs under Un*x, the first getchar() reads the newline, the second getchar() reads the first character of the first input, therefore your code gives the wrong output. You can simply use gets(line) again to get rid of the newline.
Hope this will make your code AC

[I LIKE GN]

sorry 4 late reply...
the code was modified...
still wa

Code: Select all

#include <stdio.h> 
char flag, formed, line[130]; 
int count; 

void read(char prev, char *t, char X){ 
   if( flag )return ; 
   char s, x = true; 
   s = X? X: line[count++]; 

   if( (s=='\r' || s=='\n' || s == -1) && prev == -1 ){formed = 1; return;} 

   if( s == ')' && prev !='(' || s==']' && prev!='[' ){ 
      flag = true; 
      return ; 
   } 
   if( s == ')' || s==']' ){ 
      *t = false; 
      return; 
   } 
   if(s=='\r' || s=='\n'){ 
      formed = flag = true; 
      return; 
   } 
   read(s, &x, 0); 
   if(x && flag==0){ 
      s = line[count++]; 
      /* it must be closing sequence */ 
      if(s=='\r' || s=='\n'){ 
         formed = flag = true; 
         return; 
      } 
      while( s == '(' || s == '[' ){ 
         read(prev,&x, s); 
         s = line[count++]; 
      } 
   } 
} 

void main(void){ 
   //freopen("i:\\a\\673.txt","rb",stdin); 

   int cas; char t; 

   scanf("%d", &cas); t = getchar(); 
   while( cas--) { 
      gets( line ); 
      if( line[0] == '\n' || line[0] == 13 ){ 
         puts("Yes"); 
      } 
      else{ 
         count = 0; 
         flag = formed = false; t = -1; 
         while( !formed && !flag ){ 
            read(-1, &t, 0); 
         } 
         flag?puts("No"):puts("Yes"); 
      } 
   } 
} 

please help...

[b]

this is my code.i dont understand why wa.plz help me.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

main()
{
char t[200],t1[200],t2[200],t3[200],t4[200];
char t5[200];
int i,j,k,m=0,n=0,l,check=0,check1=0,k1=0,k2=0,m1=0,m2=0,m3=0,m4=0;
char s[200];
int k3,k4;
long p;
p=atol(gets(s));
for(l=0;l<p;l++)
{
gets(t);

i=strlen(t);
if(i==0)
{
printf("Yes\n");
continue;
}
for(j=0;j<i;j++)
{
if(t[j]=='(')
{
m++;
k1=strlen(t1);
k2=strlen(t2);
if(k1<k2)
{
printf("No\n");
check=1;
k1=0;k2=0;k3=0;k4=0,m1=0,m2=0,m3=0,m4=0;
break;
}
else
t1[m1++]='(';


t1[m1]='\0';
}
else if(t[j]=='[')
{
n++;
k3=strlen(t3);
k4=strlen(t4);
if(k3<k4)
{
printf("No\n");
check=1;

k1=0;k2=0;k3=0;k4=0,m=0,n=0,m1=0,m2=0,m3=0,m4=0;

break;
}
else
t3[m4++]='[';

t3[m3]='\0';
}
else if(t[j]==')')
{
k1=strlen(t1);
k2=strlen(t2);
if(k1<k2)
{
printf("No\n");
check=1;
k1=0;k2=0;k3=0;k4=0,m=0,n=0,m2=0,m1=0,m3=0,m4=0;

break;
}
else
t2[m2++]=')';
t2[m2]='\0';
m--;
}
else if(t[j]==']')
{
k3=strlen(t3);
k4=strlen(t4);
if(k3<k4)
{
printf("No\n");
check=1;

k1=0;k2=0;k3=0;k4=0,m=0,n=0,m1=0,m2=0,m3=0,m4=0;

break;
}
else
t4[m4++]=']';
t4[m4]='\0';
n--;
}
}
if(check!=1&&m==0&&n==0)
printf("Yes\n");
else
{
m=0;
n=0;
m1=0;m2=0;m3=0;m4=0,k1=0,k2=0,k3=0,k4=0;
check=0;
continue;
}
}
}

[ayon]

your program gives wrong answers in almost every cases, even () or [] gives wrong answer, better try with stack, by using stack this problem can be solved in 7-8 lines.

[jan_holmes]

Yeah... using STL is possible,but when I submitted my code using STL,I got a very2 slow AC..... Maybe using Bruteforce could reduce the runtime... Hope it helps...

[Timo]

I think this problem can be solved easily if you use stack.

- scan the string from left to right
- if find '(' or '[' push them into your stack
- if find ')' or ']' and the top of the stack is not they match then break from
the looping the answer is "No". Otherwise pop from the stack
- after you finished scan the string but the stack is not empty then the answer
is "No", otherwise "Yes".

I hope you understand what I mean and can get AC.

[Roby]

Here are some input for your program:

Code: Select all

4
([])
(([()])))
([()[]()])()
[(])

The output should be:

Code: Select all

Yes
No
Yes
No

[jjtse]

I don't think '{' and '}' can be a valid input character.

INPUT:
The file contains a positive integer n and a sequence of n strings of parentheses () and [], one string a line.

[jjtse]

can there be spaces between characters in the input string?


i.e. : "([]) []"

[ayon]

no, there cant be any spaces between the characters. bcos it is said that the string consisting of parentheses () and []. surely there wont be any '{' or '}'

[Roby]

Yes, the input wouldn't have '{' and '}'. I've mistaken for read the problem description (lucky me, my code give me AC). And there also wouldn't any spaces given in the input.

Code: Select all

The file contains a positive integer n and a sequence of n strings of parentheses () and [], one string a line.

Sorry...

[Wei-Ming Chen]

What's wrong?

#include <stdio.h>
#include <string.h>
int main()
{
int a,b,e,f,g,h;

[ayon]

for input
)(
output must be "No"