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

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 »

Try the following input:

Code: Select all

2
([]))
Then see, what will happen?
bye

nameofevil
New poster
Posts: 2
Joined: Sun Feb 25, 2007 4:01 pm

Post by nameofevil »

i see, :) Thx

jainal cse du
New poster
Posts: 23
Joined: Thu Jul 27, 2006 2:43 pm
Location: University of Dhaka,Bangladesh

Post by 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
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim »

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

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

To jainal cse du ...

Post by 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.
regards,
nymo

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by 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 != 0; i++)
{
if (s == '(')
{
st++;
stack[st] = s;
} else
if (s == '[')
{
st++;
stack[st] = s;
} else
if (s == ')')
{
if (stack[st] != '(') b = 0;
st--;
} else
if (s == ']')
{
if (stack[st] != '[') b = 0;
st--;
}
if (st < 0) b = 0;
}
if (st != 0) b = 0;
if (b)
puts("Yes");
else
puts("No");
}
}
[/code]

spider_6765
New poster
Posts: 9
Joined: Sun Jan 08, 2006 9:57 pm

Post by spider_6765 »

try this input set. May be its with your algorithm...
your code generates wrong output for these inputs.
for everycase in the following input set your code should print No
4
(])
[)]
[)(]
[))((]
(]][[)

spider_6765
New poster
Posts: 9
Joined: Sun Jan 08, 2006 9:57 pm

Post by spider_6765 »

using bool as a variable will result in compile error.
change 'bool' into 'boool' or 'booool' or anything else. :lol:

n e way.. you will get a WA once you correct this problem. check your algo to solve it.

and remember... DONOT use int, long, double etc as variable NAMES because these are variable TYPES;

spider_6765
New poster
Posts: 9
Joined: Sun Jan 08, 2006 9:57 pm

Post by spider_6765 »

your code doesn't show the right outputs for this inputs

Code: Select all

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

thomas1016
New poster
Posts: 19
Joined: Mon May 29, 2006 4:12 pm

Thx

Post by thomas1016 »

Thanks a lot .
A blank line is truly a critical input !!!!

:P :P :P

Mata
New poster
Posts: 18
Joined: Mon Dec 17, 2007 11:35 pm
Location: Queretaro
Contact:

wa

Post by Mata »

hi, I try the input in the forum, but I got wa, here is my code, what could be wrong my program?.

Code: Select all

got Ac

mukit_sust
New poster
Posts: 1
Joined: Wed May 07, 2008 11:56 am

673 wa

Post by mukit_sust »

ac
Last edited by mukit_sust on Wed May 07, 2008 11:26 pm, edited 1 time in total.

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 673 (dont open a new thread.......just search the prob. num.

Post by kbr_iut »

dont open a new thread as there is already many threads...think about that.
however ur program gives wrong output for this set of input.
input:

Code: Select all

7
([])
(([()])))
([()[]()])()
([)]
(
()(
[()
ur output is:

Code: Select all

Yes
No
Yes
Yes
No
No
No

My AC program gives:

Code: Select all

Yes
No
Yes
No
No
No
No

Hope it will help.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

vivgrn
New poster
Posts: 6
Joined: Sat Aug 25, 2007 4:48 pm

Re: 673 - Parentheses Balance

Post by vivgrn »

dear all
I have been troubled for the past few weeks solving this problem and have applied all tricks that have been given in the forum.
Yet I have been unable to get an AC.
My code is as follows

Code: Select all

#include<iostream>
#include<stack>
#include<cstdio>
using namespace std;

int main()
{

int n;
cin>>n;
fflush(stdin);
while(n>0)
{
          char str[129];
          stack<char> s;
          gets(str);
         
          
          if(strlen(str)!=0)
          {
          int i=0;
          bool flag=true;
          while(flag==true && i<strlen(str))
          {
                           if(str[i]=='('||str[i]=='[')
                           {s.push(str[i]);i++;}
                           else 
                           {
                                          if(str[i]==']')
                                          {
                                                       if(!s.empty())
                                                       {
                                                         if(s.top()=='[')
                                                         {
                                                         s.pop();
                                                         i++;
                                                         }
                                                         else
                                                         {
                                                             flag==false;
                                                             break;
                                                         }
                                                       }
                                                       else
                                                       {
                                                       flag=false;
                                                       break;
                                                       }
                                          }
                                          if(str[i]==')')
                                          {
                                                         if(!s.empty())
                                                         {
                                                         if(s.top()=='(')
                                                         {
                                                         s.pop();
                                                         i++;
                                                         }
                                                         else
                                                         {
                                                             flag==false;
                                                             break;
                                                         }
                                                         }
                                                         else
                                                         {
                                                             flag=false;
                                                             break;
                                                         }
                                          }
                           }
          }      
          if(s.empty()&&i==strlen(str))
          cout<<"Yes"<<endl;
          else
          cout<<"No"<<endl; 
          }
          else
          cout<<"Yes"<<endl;                                          
          n--;
}


return 0;
}
I would request you to kindly go through the code and tell me where does the problem lie.
Thanking you in advance.

Samudra Banerjee
New poster
Posts: 4
Joined: Mon Jun 16, 2008 7:21 am
Location: Kolkata, India
Contact:

Re: 673 - Parentheses Balance

Post by Samudra Banerjee »

Always getting a Wrong Answer for this code.....I have tried all possible test cases..Can anyone please help ?

Code: Select all

#include<stdio.h>
#include<string.h>
int main()
{
    char c,s[129],stack[129];
    int sp=-1,i,j,n,l,k;
    scanf("%d",&n);
    c=getchar();
    for(i=1;i<=n;i++)
    {
     sp=-1;k=0;
     while(1)
     {
      c=getchar();
      s[k++]=c;
      if(c=='\n' || c==EOF) {s[k]='\0';break;}
     }
     l=strlen(s);
     for(j=0;j<l;j++)
     {c=s[j];
     if(c=='[' || c=='(') stack[++sp]=c;
     else if(c==')') if(sp>=0 && stack[sp]=='(') sp--;
                     else break;
     else if(c==']') if(sp>=0 && stack[sp]=='[') sp--;
                     else break;
     }
     if(j==l && sp==-1) printf("Yes\n"); else printf("No\n");
    }
    return 0;
}
Jodi Tor Dak Shune Keu Naa Ashey....
Tobey Ekla Cholo Re....

Post Reply

Return to “Volume 6 (600-699)”