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

kcode
New poster
Posts: 8
Joined: Sun Mar 22, 2009 6:24 am
Location: Aryadesa

Re: 673 - Parentheses Balance

Post by kcode »

mf wrote:Try "((" or "))".

And your code is too complex for such an easy task, too many if's. Keep it simpler :)
Got AC. Wasnt checking stack empty. Would try to make it simpler, thanks.

ashraf_iut
New poster
Posts: 3
Joined: Thu Jan 22, 2009 9:16 pm

673.Plz help me..Why Not AC!!

Post by ashraf_iut »

I am not clear what is the problem??I am getting correct Ans for so many critical input ..But it is not AC..
Am I correct in my Conception?? plz help me..

#include<iostream>
#include<algorithm>
#include<stack>
#define max 130
using namespace std;
char str[max];
bool flag;
int main(){
int i,j,tc;
//freopen("673.txt","r",stdin);
scanf("%d",&tc);
for(i=0;i<tc;i++){
stack<char>F;
stack<char>S;
scanf("%s",str);
//if(strlen(str)==0){printf("No\n");continue;}
flag=true;
for(j=0;j<strlen(str);j++){
if(str[j]=='(')F.push(str[j]);
else if(str[j]=='[')S.push(str[j]);
else if(str[j]==')'){
if(F.empty()){
flag=false;
break;
}
F.pop();
}
else if(str[j]==']'){
if(S.empty()){
flag=false;
break;
}
S.pop();
}
}
if(flag){
if(F.empty() && S.empty())
printf("Yes\n");
else printf("No\n");
}
else printf("No\n");
}
return 0;
}

satyaanveshi
New poster
Posts: 2
Joined: Fri Dec 11, 2009 4:28 pm

Re: 673 - Parentheses Balance

Post by satyaanveshi »

Hi,
I have got correct output for all the test cases I could find, but still get WA. What all is possible in the input? I changed the code for ignoring spaces also. Anyone any idea? I am new to UVA, it would be very kind if someone can help me out.
Thanks a lot.

Code: Select all

#include <iostream>
#include <stack>
#include <queue>
#include <string.h>
#include <math.h>
#include <vector>
#include <stdio.h>
#define MAX 1000
using namespace std;
int main()
{
	int test,senti,str_len;
	cin>>test;
	getchar();
	char str[MAX];
	stack<char> stk;
	char a;
	for(int j=1;j<=test;j++)
	{

		cin.getline(str,1000);  
		str_len=strlen(str);
		stack<char> stk;
		senti=0;
		
		for(int i=0;i<str_len;i++)
		{
			if(str[i]!='(' && str[i]!=')' && str[i]!='[' && str[i]!=']')
			continue;
			
			if(str[i]=='(' || str[i]=='[')
			stk.push(str[i]);
			
			if(stk.empty())
			{
				senti=1;
				break;
			}
			
			if(str[i]==')'	&& stk.top()!='(')
			{
				senti=1;
				break;
			}
			
			if(str[i]==']'	&& stk.top()!='[')
			{
				senti=1;
				break;
			}
			
			if( (str[i]==')' && stk.top()=='(') || ( str[i]==']' && stk.top()=='[' ))
			stk.pop();
						
		}
		
		if(senti==0 && stk.empty())
		cout<<"Yes";
		else
		cout<<"No";
		
		if(j!=test)
		cout<<endl;
	}
}

mehrab
New poster
Posts: 10
Joined: Sat Jul 03, 2010 3:04 pm

673 - parenthesis balance

Post by mehrab »

i'm getting wrong answer for the following code ... any help would be appreciated....
is my logic correct for the following code...

Code: Select all

//parenthesis balance
#include <stdio.h>

int main()
{
	char ch[128];
	int cas,i,j,a,b;
	int sum1,sum2;

	scanf("%d",&cas);

	for(i=0;i<cas;i++)
	{
		scanf("%s",&ch);

		sum1=0,sum2=0;

		for(j=0;ch[j]!='\0';j++)
		{
			if(ch[j]>90)
			sum1+=ch[j];
			else
			sum2+=ch[j];
		}
		if(sum1%2==0)
		a=1;
		else
		a=0;


		if(sum2<81)
		{
			if(sum2==0)
			b=1;
			else
			b=0;
		}

		else
		{
			if(sum2%81==0)
			b=1;
			else
			b=0;
		}


		if(a*b==1)
		printf("Yes\n");
		else
		printf("No\n");

	}
	return 0;
}[code]

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 673 - parenthesis balance

Post by sohel »

Have you looked at other discussion related to this problem. Like, http://acm.uva.es/board/viewtopic.php?f=7&t=12707
Don't create a new thread for a problem that already exists!

@mjad
New poster
Posts: 44
Joined: Thu Jul 22, 2010 9:42 am

Why 673 WA?

Post by @mjad »

AC
Last edited by @mjad on Thu Nov 04, 2010 3:09 am, edited 1 time in total.

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 673 - Parentheses Balance

Post by sazzadcsedu »

You have problem in reading input.When you have to consider empty string you need to use gets().So use gets.and when you use gets() keep one thing in mind you have to read a dummy string if you take input before for taking newline.Like :

Code: Select all

  scanf("%d",&n);
   
   gets(text); //dummy input
   for(j=1;j<=n;j++)
   {
   
      o=0;
      input[o]='\0';
       //scanf("%s",text);
        
      gets(text);
     

   }
Because you are pressing enter character after taking input for n if you not take dummy input your (text string) will not get the correct input.Everything except it , is ok.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

@mjad
New poster
Posts: 44
Joined: Thu Jul 22, 2010 9:42 am

Re: 673 - Parentheses Balance

Post by @mjad »

:D Thanks for Help
i got AC

ujjal.ruet
New poster
Posts: 15
Joined: Thu Sep 02, 2010 3:10 pm
Location: Dhaka,Bangladesh
Contact:

Re: 673 - Parentheses Balance

Post by ujjal.ruet »

I don't know where is my problem.I m getting WA in this problem. I have used stack to solve this problem.
Thanks in advanced.


EDIT: I got AC.It was a silly mistake.

wawa
New poster
Posts: 5
Joined: Thu Dec 16, 2010 8:17 am

Re: 673 - Parentheses Balance

Post by wawa »

Code: Select all

#include <iostream>
#include <string>
using namespace std;
int main()
{
	int n, stk, stack[128], check, wrong;
	string str;
	cin >> n;
	cin.ignore (80, '\n');
	for (int i = 0; i < n; i++)
	{
		getline(cin, str);
		if (str == "")
			stk = 0;
		else
		{
			stk = 0;
			wrong = 0;
			for (int j = 0; j < str.size(); j++)
			{
				if (str[j] == '(')
				{
					stack[stk] = 41;
					stk++;
				}
				else if (str[j] == '[')
				{
					stack[stk] = 93;
					stk++;
				}
				else if (str[j] == ')')
				{
					if (stack[stk - 1] == 41)
						stk = stk - 1;
					else
					{
						wrong = 1;
						break;
					}
				}
				else if (str[j] == ']')
				{
					if (stack[stk - 1] == 93)
						stk = stk - 1;
					else
					{
						wrong = 1;
						break;
					}
				}
			}
		}
		if (stk == 0 && wrong == 0)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	return 0;
}
Why kept getting WA...?????

anik.bit0104
New poster
Posts: 6
Joined: Thu Sep 23, 2010 1:50 pm
Location: Dhaka, Bangladesh

Re: 673 - Parentheses Balance

Post by anik.bit0104 »

Code: Select all

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

int main()
{
  stack <char> bracks;
  char c;
   string s;
  long unsigned numOfTestCase;

   cin>>numOfTestCase;

  for (long unsigned i=0;i<numOfTestCase ; i++)
  {
      cin>>s;
      for (int i=0;i<s.length() ; i++)
    {
   
      if (bracks.empty())
        {
          bracks.push(s[i]);
         }


      else if (bracks.top()=='(' && s[i]==')' || bracks.top()=='[' && s[i]==']')
        {
             bracks.pop();

        }

      else if(s[i]=='(' || s[i]==')' ||  s[i]=='[' || s[i]==']')
        {
             bracks.push(s[i]);

        }
    }

  if (bracks.empty()) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;

  while(!bracks.empty()){bracks.pop();}
  }
  return 0;
}


What's wrong with my code? its correct for every input set mentioned here..

marjan
New poster
Posts: 3
Joined: Tue Nov 01, 2011 11:54 am

Re: 673 - Parentheses Balance

Post by marjan »

I don't know how that macro exactly works,but seems it doesn't wrap stdio.h? Those using statements between _STD_BEGIN and _STD_END import those names into the std namespace. They would now be available both as size_t and std::size_t (don't ask me why they should be kept visible globally). - The C++ versions have other differences. For example, it appears that some things are macros in C libraries, which C++ redefines as normal functions. Also, <cmath> adds various overloads to functions (no overloading in C)

cjahangir
New poster
Posts: 1
Joined: Fri Dec 09, 2011 8:27 pm

Re: 673 - Parentheses Balance

Post by cjahangir »

#include<stdio.h>
#include<string.h>
char stack[200];
long top;
char pop();
char push(char c);
int main()
{
long i,l,n,j,k;
char c[200];
scanf("%ld",&n);

for(i=0;i<n;i++)
{
top=0;k=0;
if(i==0)
scanf("%c",&c[0]);
gets(c);
l=strlen(c);

stack[top]=c[0];

for(j=1;j<l;j++)
{
if(stack[top]=='('&&c[j]==')')
pop();
else if(stack[top]=='['&&c[j]==']')
pop();
else push(c[j]);
if(top<0&&j==l-1)
{printf("Yes\n");k=1;}
}
if(k==0)
printf("No\n");
}
return 0;
}

char push(char c)
{
top=top+1;
stack[top]=c;

}
char pop()
{
top=top-1;
}




guys .. please check ma code. i am getting rong answer.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 673 - Parentheses Balance

Post by brianfry713 »

cjahangir, check your code with an empty string for an input. Also use the code blocks when posting.
Check input and AC output for thousands of problems on uDebug!

cse.mehedi
New poster
Posts: 36
Joined: Sun Mar 18, 2012 8:18 am

Re: 673 why RE???

Post by cse.mehedi »

Help me plz! :(

Code: Select all


#include<stdio.h>
#include<iostream>
#include<string.h>
int form(char s[10])
{
    int formt=0,n=1;
    for(int i=strlen(s)-1;i>=0;i--)
    {
        formt=formt+(s[i]-48)*n;
        n*=10;
    }
    return formt;
}

int main(void)
{

    using namespace std;
    char str[100],n[10];
    int m;
    gets(n);
    m=form(n);
    for(int p=0;p<m;p++)
    {
        gets(str);
        int num1=0,num2=0;
        for(int i=0;i<strlen(str);i++)
        {
        if(str[i]=='('||str[i]=='[')
        num1++;
        else if(str[i]==')'||str[i]==']')
        num2++;
        }
        if(num1==num2 && num1!=0 && num2!=0)
        printf("Yes\n");
        else printf("No\n");
    }
}


Post Reply

Return to “Volume 6 (600-699)”