673 - Parentheses Balance

[kcode]

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]

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]

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]

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]

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]

AC

[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.

[@mjad]

Thanks for Help
i got AC

[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]

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]

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]

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]

#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]

cjahangir, check your code with an empty string for an input. Also use the code blocks when posting.

[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");
    }
}