673 - Parentheses Balance

[LMG]

I tried to use stack to implement the work and my code got correct answers always. I don't know where is the bug. Can somebody help me?

#include <stdio.h>
#include <string.h>
main()
{
char stack[130];
char c[130];
char s[130];
int n;
int i, j;
int len;
scanf("%d\n", &n);
for(i=0; i<130; i++)
{
stack[i]='\0';
s[i]='\0';
c[i]='\0';
}
while(n>0)
{
gets(s);
len=strlen(s);
for(i=0; i<len; i++)
c[i]=s[i];
j=0;
for(i=0; i<len; i++)
{
if(c[i]=='(')
{
stack[j]=c[i];
j++;
}
else if(c[i]=='[')
{
stack[j]=c[i];
j++;
}
else if(c[i]==')')
{
if(stack[j-1]=='(')
{
j--;
stack[j]='\0';
}
else
{
j--;
break;
}
}
else if(c[i]==']')
{
if(stack[j-1]=='[')
{
j--;
stack[j]='\0';
}
else
{
j--;
break;
}
}
}
if(j==0)
printf("Yes\n");
else
printf("No\n");
n--;
}
}

[felipealmeida]

i also got WA and i can't see any mistake

ps: i wrote it in portuguese, so
pilha = stack
topo = top
vet = array
entrada = input

[code]
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX 128

#define PAR 0
#define COL 1

typedef struct _pilha
{
int vet[MAX];
int topo;
} pilha;

void inipilha(pilha *p)
{
p->topo = -1;
}

int topo(pilha p)
{
return p.vet[p.topo];
}

void push(pilha *p, int valor)
{
(p->topo)++;
p->vet[p->topo] = valor;
}

int pop(pilha *p)
{
int valor = p->vet[p->topo];
(p->topo)--;

return valor;
}

int main(void)
{
pilha p;

char entrada[MAX];

char sqtd[MAX];
int qtd;

int i;
int j;


fgets(sqtd, MAX, stdin);
qtd = atoi(sqtd);

for (i = 0; i < qtd; i++)
{
inipilha(&p);
fgets(entrada, MAX, stdin);
entrada[strlen(entrada)-1] = '\0';

for (j = 0; j < strlen(entrada); j++)
{
if (entrada[j] == '(')
{
push(&p, PAR);
}
else if (entrada[j] == '[')
{
push(&p, COL);
}
else if (entrada[j] == ')' && p.topo >= 0 && topo(p) == PAR)
{
pop(&p);
}
else if (entrada[j] == ']' && p.topo >= 0 && topo(p) == COL)
{
pop(&p);
}
else
{
p.topo = -2; /* um numero qualquer para dizer que t

[felipealmeida]

I always get WA when I submit, but I can't see any mistake.
I've tried many different inputs and all of them I've got correct answer.

my code:

Code: Select all

* edited *


[seulkiro]

Try the following input:

Code: Select all

(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((())))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))

64 open brackets and 64 close brackets.

I think the answer should be Yes, since the maximum string length is 128 according to the description.

[felipealmeida]

thank you very much!

string length wasn't large enough...

[uvapotta]

I got Run time error in my code but test but it pass all test that i have done
Can any one help me?

Code: Select all

#define DIM 129
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main()
{
   int i=0,col=0,j,n,par=0;
   char **string,*e;
   
   scanf("%d",&n);
   gets(e);
   string = (char **) malloc (n * sizeof(char *));    
   for (i=0; i<DIM; i++)
     {
        *(string +i) = (char *) malloc(DIM * sizeof (char));
     }
     
   for(j=0;j<n;j++){
     gets(string[j]);
    }

   for(j=0;j<n;j++)
   {      
      par=0; col=0;
   
      {
      for(i=0;i<DIM;i++)
      {
               
         if( string[j][i] == '(')
         {
            par++;
         }
         
         if( string[j][i] == ')')
         {
            par--;
         }
         
         if( string[j][i] == '[')
         {
            col++;
         }
         
         if( string[j][i] == ']')
         {
            col--;
         }
         if((col <0) || (par <0) || (string[j][i] == '\0') )
         {
         break;
         }
         
                      
   
       }
       }
   if((par == 0) && (col == 0))
      puts("Yes");
   
   else puts("No");
   }
   
   
   
   
      
   return 0;
}


[/code]

[Jan]

Search your problem in the board first. If you find a thread then try to post in that thread. Dont open a new thread if there is one already.

[uvapotta]

Ok Sorry I will post there

[nameofevil]

I also got WA with my code, and it seem correct in all sample inputs I fund in this forum. plz help

Code: Select all

#include<stdio.h>
#include<string.h>
int main(){
   int N,index,stop,string[130];
   bool res;
   char str[130] ;
   if(fgets(str,129,stdin) == NULL){
      return 1;
   }
   sscanf(str,"%d\n",&N);
   while(N--){
      index = stop = 0;
      res = true;
      for( ;  res && stop == 0 ; ){
         switch(getchar()){
            case '\n':
               stop = 1;
               break;
            case '(':
               string[index++] = 1;
               break;
            case '[':
               string[index++] = 2;
               break;
            case ')':
               if(index == 0 || (index>0 && string[--index] != 1) ){
                  res = false;
               }
               break;
            case ']':
               if(index == 0 || (index>0 && string[--index] != 2) ){
                  res = false;
               }
               break;
            default:
               break;
         }
      }
      if(index == 0 && res ){
         fprintf(stdout,"Yes\n");
      }else{
         fprintf(stdout,"No\n");
      }
   }
}


[/code]

[asif_rahman0]

Try the following input:

Code: Select all

2
([]))


Then see, what will happen?
bye

[nameofevil]

i see, Thx

[jainal cse du]

Can Anybody Tell me Why I am getting RE?

Code: Select all

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

int main()
{
       char str[150];

       int top = 0,i,n;
       char stack[150];
       scanf("%d%*c",&n);
       while(n--)
       {

          gets(str);
          int left = 0;
          int right = 0;
          for(i = 0; str[i]; i++)
          {

             if( (str[i] == '(') || (str[i] == '[') )
             {        stack[top++] = str[i];
            left++;
             }

             if( (str[i] == ')') )
             {
                if( stack[--top] == '(' )
               right++;
                else
               break;

             }
             if( (str[i] == ']') )
             {
                if(stack[--top] == '[')
               right++;
                else
               break;
             }
          }
          if(left == right)
             printf("Yes\n");
          else
         printf("No\n");
       }
       return 0;
}


Advance Thanks

[shamim]

You have to set top=0 before each case.
This correction will give you wrong answer.

[nymo]

To jainal cse du,
I just skim through your code, not going thorougly ...
however, your code breaks when a mismatching end bracket occurs... think about a test case when upto the mismatching end bracket (left == right) ; your code will output Yes though it shouldn't.

[hamedv]

what's wrong with my code?


#include <stdio.h>

int i, st, stack[129], t, l;
bool b;
char s[129];

int main()
{
scanf("%d", &t);
for (l = 0; l < t; l++)
{
scanf("%s", &s);
st = 0;
b = 1;
for (i = 0; s[i] != 0; i++)
{
if (s[i] == '(')
{
st++;
stack[st] = s[i];
} else
if (s[i] == '[')
{
st++;
stack[st] = s[i];
} else
if (s[i] == ')')
{
if (stack[st] != '(') b = 0;
st--;
} else
if (s[i] == ']')
{
if (stack[st] != '[') b = 0;
st--;
}
if (st < 0) b = 0;
}
if (st != 0) b = 0;
if (b)
puts("Yes");
else
puts("No");
}
}
[/code]