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
Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen »

I made a very very silly mistake.....

I wanted to write "&&" , but wrote "||" instead.....

Thanks Ayon, you helped me solve this problem.

fayyazkl
New poster
Posts: 11
Joined: Thu Mar 16, 2006 8:02 am
Location: Lahore, Pakistan

673 How use cin in C++

Post by fayyazkl »

It seems quite silly to answer a post two years old. But i thought just in case.... :)

HERE IS THE POST

Zhao Le wrote:

I have occurred to the same question.

I can solve when using
first gets();
then atoi();

but it is C like.

I hate to both include iostream and stdio
my question is how can I turn it to C++ iostream when occurred to the multiply input.
_________________
AC makes me feels good,
But WA makes me thinks hard.

MY RESPONSE:

# include <iostream>

int n;
char str[150];

cin >> n;
cin.ignore(); // this ignores the \n at the end of line
cin >> str; // or you might use cin.getline(str,130) as an alternate
There are 10 types of people. Those who can read binary and those who cant ;)
http://acm.uva.es/problemset/usersjudge.php?user=37504

alfreadx
New poster
Posts: 4
Joined: Fri Aug 04, 2006 11:06 am
Location: Taiwan

673 , RE why??

Post by alfreadx »

Code: Select all


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

stack<char> x;
bool judge(char *in)
{
	static int i,len;

	while(!x.empty())	x.pop();
	
	len=strlen(in);
	if(in[0] == ']' || in[0] == ')')	return 0;
	if(len % 2 != 0)	return 0;
	for(i=0;i<len;++i){
		switch(in[i]){
			case '[':
			case '(':	x.push(in[i]);	break;

			case ']':	if(x.top() == '[')	x.pop();
						else 	return 0;
						break;
			case ')':	if(x.top() == '(')	x.pop();
						else 	return 0;
						break;
			default : break;
		}

	}
	if(x.empty())	return 1;
	else return 0;

}
int main()
{
	int j,times;
	char in[130];

	times=atol(gets(in));
	for(j=0;j<times;++j){
		gets(in);

		if(judge(in))	cout << "Yes\n";
		else cout << "No\n";


	}


    system("pause");
    return 0;
}
i submit code , but i got RE , why ??
can you help me find bug .
thank you.

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes »

remove "system("pause")" from your code.

alfreadx
New poster
Posts: 4
Joined: Fri Aug 04, 2006 11:06 am
Location: Taiwan

oh! thank you!!

Post by alfreadx »

oh ! thank you !!

but i got RE .

thanks again.

who can help me find bug in my code .

thank you.

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes »

try this input :
1
(()))(
The answer should be "No".

LMG
New poster
Posts: 2
Joined: Sun Aug 20, 2006 11:35 pm

673 WA

Post by 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='\0';
s='\0';
c='\0';
}
while(n>0)
{
gets(s);
len=strlen(s);
for(i=0; i<len; i++)
c=s;
j=0;
for(i=0; i<len; i++)
{
if(c=='(')
{
stack[j]=c;
j++;
}
else if(c=='[')
{
stack[j]=c;
j++;
}
else if(c==')')
{
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
New poster
Posts: 3
Joined: Tue Oct 03, 2006 2:49 pm

Post by felipealmeida »

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

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

Code: Select all

#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
New poster
Posts: 3
Joined: Tue Oct 03, 2006 2:49 pm

673 - Parentheses Balance

Post by 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 *
Last edited by felipealmeida on Tue Nov 14, 2006 6:45 pm, edited 2 times in total.

seulkiro
New poster
Posts: 6
Joined: Sun Feb 15, 2004 2:13 am
Location: Canada
Contact:

Post by 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.
waikiki..

felipealmeida
New poster
Posts: 3
Joined: Tue Oct 03, 2006 2:49 pm

Post by felipealmeida »

thank you very much!

string length wasn't large enough...


:D
Undergraduating in Computer Science
Federal University of Rio de Janeiro

uvapotta
New poster
Posts: 2
Joined: Fri Dec 08, 2006 12:21 am

673

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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.
Ami ekhono shopno dekhi...
HomePage

uvapotta
New poster
Posts: 2
Joined: Fri Dec 08, 2006 12:21 am

Post by uvapotta »

Ok Sorry I will post there

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

Post by 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]

Post Reply

Return to “Volume 6 (600-699)”