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
.pandre.
New poster
Posts: 9
Joined: Mon Nov 08, 2004 10:58 pm
Location: Coimbra, Portugal

Post by .pandre. » Wed Nov 10, 2004 10:36 pm

[/quote]
Have you tried the special case of empty lines as input?
[/quote]

yes I have tried the empty string case and had the correct answer ("Yes")
And doesn't s.substring(i+2) give an exception when applied at the end of the string s?
no, no problem there :(


but I finnally got AC, i think the problem was that the number that I was passing to ReadLn() was too small, (in the accepted version, I used 50 for the number n (wow, they really use BIG numbers):
int n = Integer.parseInt(ReadLn(50).trim())

really stupid thing, don't you think?

anyway, thanks a lot for your time, i really apreciated your help

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac » Thu Nov 11, 2004 1:32 am

I don't think the judge uses numbers of more than 25 digits for the number of test cases.. are you sure that this is the only change you made before getting AC? Well, congrats anyway and no problem, keep up the good work :)

.pandre.
New poster
Posts: 9
Joined: Mon Nov 08, 2004 10:58 pm
Location: Coimbra, Portugal

Post by .pandre. » Thu Nov 11, 2004 2:50 am

Maniac wrote:I don't think the judge uses numbers of more than 25 digits for the number of test cases.. are you sure that this is the only change you made before getting AC? Well, congrats anyway and no problem, keep up the good work :)
yes, it was the only change ! quite weird, ins't it? well but that's an AC and that's what matters when we're so worried
once again thanks

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac » Thu Nov 11, 2004 1:39 pm

for your convenience and to avoid these problems in the future, there is also a readline function witch doesn't take a length-parameter but just reads a line of arbitrary length. See the forum-thread 'Java useful methods to save time'.

faisneaz
New poster
Posts: 2
Joined: Tue Jun 29, 2004 7:27 pm

673

Post by faisneaz » Tue Dec 28, 2004 1:11 am

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

main()
{
char str[1000000],str1[1000000],c;
int a,b,size=0,counter=0,bool;
scanf("%d",&counter);
while(counter>0)
{
size=0;
bool=0;
scanf("%s",str);
//a=strlen(str);
if(strlen(str)==0)
{
printf("Yes\n");
}
else
{
for(b=0;str!='\0';++b)
{
if(str=='('||str=='[')
{
str1[size]=str;
str1[++size]='\0';
}
if(str==')'||str==']')
{
--size;
if((str==')'&&str1[size]!='(')||(str==']'&&str1[size]!='['))
{
if(strlen(str1)==0)
{
++bool;
}
break;
}
else
{
str1[size]='\0';
}
}
}
if(strlen(str1)!=0||bool>0)
{
printf("No\n");
bool=0;
}
else
{
printf("Yes\n");
}
}
--counter;
}
return 0;
}

Karthekeyan
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Location: IITM,chennai,Tamil Nadu,India
Contact:

673

Post by Karthekeyan » Sat Feb 26, 2005 2:21 pm

Here's my code for the problem 673. I dunno why i am getting wrong answer again and again for this problem. Can someone help me?

Code: Select all

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;

vector <char> st;
int check(char ch[200])
{
  int ans=1;
  int c=strlen(ch);
  for(int i=0;i<c;i++)
    {
      {
	if((ch[i]=='(')||(ch[i]=='['))
	  st.push_back(ch[i]);
	else
	  {
	    if(ch[i]==')')
	      {
		if(st.size()==0)
		  {
		    ans=0;
		    break;
		  }
		if(st.back()=='(')
		  st.pop_back();
		else
		  {
		    ans=0;
		    break;
		    }
		}
	      else
	      if(ch[i]==']')
		{
		  if(st.size()==0)
		    {
		      ans=0;
		      break;
		    }
		  if(st.back()=='[')
		    st.pop_back();
		  else
		    {
		      ans=0;
		      break;
		    }
		}
	    }
	}
    }
  if((st.size()!=0)||(ans==0))
    {
      cout<<"No\n";
      return 0;
    }
  else if((st.size()==0)&&(ans==1))
    {
      cout<<"Yes\n";
      return 1;
    }
}
main()
{
  int N,a;
  cin>>N;
  while(N>0)
    {
      st.clear();
      N--;
      char ch[200];
      cin>>ch;
      a=check(ch);
    }
}

thanx in advance
Karthe

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Mon Feb 28, 2005 2:34 pm

For this inputs

Code: Select all

3
((()

())))
your out put should be

Code: Select all

no
yes
no
but your program ignores the second case

lolo
New poster
Posts: 2
Joined: Thu Mar 03, 2005 11:09 pm

673 WA Please Help meeeeeeeeeee

Post by lolo » Thu Mar 03, 2005 11:17 pm

i don't know why a got a WA
look my code and check it
please
thanks


#include <stdio.h>
#include <iostream.h>

bool EsI(char n)
{
if(n == '(' || n == '[')
return true;
return false;
}

char Contrario(char n)
{
if(n == '(')
return ')';
if(n == ')')
return '(';
if(n == '[')
return ']';
return '[';
}

int main()
{
char entrada[130] = {'\0'};
int cases , cant;

scanf("%d" , &cases);

while(cases--){

scanf("%s" ,entrada);

int contador = 0;

cant = strlen(entrada);


bool salto = false;


if(!cant){

printf("No\n");
salto = false;

}
else{

if(!(cant % 2)){

for (int i = 0 ; i < cant ; i ++){

if(EsI(entrada) && !salto){

char c = Contrario(entrada);
if(i == cant - 1){
salto = true;
}
for (int j = i + 1 ; j < cant && !salto ; j ++){

if(entrada[j] == entrada)
contador++;

if(entrada[j] == c && !contador--)
if(((j - i - 1) % 2))
salto = true;
}
contador = 0;
}
}
}
else
salto = true;
}
if(salto)
printf("No\n");
else
printf("Yes\n");
}
return 0;
}

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sat Mar 05, 2005 1:22 pm

Look at the problem description carefully
You are given a string consisting of parentheses () and []. A string of this type is said to be correct:

a)
if it is the empty string
(b)
if A and B are correct, AB is correct,
(c)
if A is correct, (A) and [A] is correct.
There may be empty string
here is a sample input

Code: Select all

3
([)]

((([[[]]])])
and output should be

Code: Select all

no
yes
no
your code ignors the empty string..

murkho
New poster
Posts: 33
Joined: Mon Mar 28, 2005 6:41 pm

673 :Please Help me Finding WA

Post by murkho » Tue Mar 29, 2005 2:32 am

/*@BEGIN_OF_SOURCE_CODE*/

//No: 673...
//parenthess Balance.....


#include<stdio.h>

int main()
{
char str[150],*p,copy[150],ch;
int i,j,n,index = -1,flag;
fflush(stdin);
//freopen("c:\\673.txt","r",stdin);
scanf("%d",&n);
for(i = 1;i<=n;i++)
{
fflush(stdin);
gets(str);
flag = 0;
index = -1;
p = str;
while(*p)
{
if(*p =='(' || *p == '[')
{
ch = *p;
copy[++index] = ch; //pushing the character if it is '(' or '['.
}
if(*p ==')' || *p == ']')
{
if(index < 0 )
{
flag = 1;
break;
}

if( ( *p ==')' && copy[index] =='(') || (*p == ']' && copy[index] =='['))
{
index= index -1; //pop '(' or '[' when ')'or ']' is found..
}
else
{
flag = 1;
break;
}

}
p++;

}
if(index != -1)
flag =1;



if(flag ==1)
printf("No\n");
else
printf("Yes\n");


}


return 0;
}
/*END_OF_SOURCE_CODE*/

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

Post by L I M O N » Tue Apr 12, 2005 11:31 am

use STL stack

User avatar
valfiros
New poster
Posts: 5
Joined: Wed May 25, 2005 3:31 pm
Location: south korea

673 WA... need help.

Post by valfiros » Wed May 25, 2005 3:39 pm

Code: Select all

#include <stack>
#include <stdio.h>

using namespace std;
void sub();

void main()
{
	unsigned int case_num;
	scanf("%d",&case_num);
	for(unsigned int i=0;i<case_num;i++)
		sub();
}

void sub()
{
		stack <char> k; // stack
		unsigned int istrue=1; // flag
		char array[130];
		char * cpt;
		
		fflush(stdin);
		cpt = gets(array);

		while(*cpt != NULL)
		{
			if( (*cpt == '[') || (*cpt == '(') )
			{
				if(*cpt == '(')
					k.push(')');
				else
					k.push(']');
			}
			else if( (*cpt == ']') || (*cpt == ')') )
			{
				if(k.empty() == 1)
				{
					istrue=0;
					break;
				}
					
				if(*cpt == k.top())
					k.pop();
				else
				{
					istrue=0;
					break;
				}
			}
/*			else if( *cpt == ' ')
			{
				cpt++;
				continue;
*/			} // disabled!!!!
			else
			{
				istrue=0;
				break;
			}
			cpt++;
		}

		if (k.empty() == 0)
			istrue=0;
		if (istrue==1)
		{
			printf("Yes\n");
		}
		else
			printf("No\n");
}
i got wa... i cannot find any critical input. plz help! :cry:
Onesama daisuki!

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci » Wed May 25, 2005 5:59 pm

Hi, your algorithm is correct, your problem is an i/o problem, as you are using gets, your first case string will be the end of the line(of the number of inputs line), so add an extra gets(anything) right after the scanf were you take the number of inputs and you will get AC... :wink:

User avatar
jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

Post by jaracz » Fri Jul 01, 2005 9:31 pm

change scanf("%d",&case_num); to scanf("%d\n",&case_num); algo is fine
Regards
keep it real!

komisarskip
New poster
Posts: 2
Joined: Tue Jul 26, 2005 8:23 pm

673 wa :( please help

Post by komisarskip » Tue Jul 26, 2005 8:26 pm

#include <stdio.h>
#include <string.h>
#define N 1000

int tab[N];
int k;

int main ()
{
int x;
char znak;
k=0;
scanf("%d\n",&x);
whhile: while (x--)
{
while((znak=getchar())!='\n' && znak!=EOF)
{
if(znak=='[') tab[k++]=1;
if(znak==']') if(k==0 || tab[--k]==2) {printf("No\n");while((znak=getchar())!='\n' && znak!=EOF);goto whhile;}
if(znak=='(') tab[k++]=2;
if(znak==')') if(k==0 || tab[--k]==1) {printf("No\n");while((znak=getchar())!='\n' && znak!=EOF);goto whhile;}
}
if(k!=0) printf("No\n");
else printf("Yes\n");
k=0;
}
return 0;
}

Post Reply

Return to “Volume 6 (600-699)”