673 - Parentheses Balance

All about problems in Volume VI. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Re: 673 - Parentheses Balance

Postby kcode » Sun Oct 04, 2009 10:11 am

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.
kcode
New poster
 
Posts: 8
Joined: Sun Mar 22, 2009 6:24 am
Location: Aryadesa

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

Postby ashraf_iut » Tue Nov 17, 2009 1:27 pm

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;
}
ashraf_iut
New poster
 
Posts: 3
Joined: Thu Jan 22, 2009 9:16 pm

Re: 673 - Parentheses Balance

Postby satyaanveshi » Fri Dec 11, 2009 4:35 pm

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;
   }
}
satyaanveshi
New poster
 
Posts: 2
Joined: Fri Dec 11, 2009 4:28 pm

673 - parenthesis balance

Postby mehrab » Sun Jul 04, 2010 11:35 am

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

[code]//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]
mehrab
New poster
 
Posts: 10
Joined: Sat Jul 03, 2010 3:04 pm

Re: 673 - parenthesis balance

Postby sohel » Sun Jul 04, 2010 10:45 pm

Have you looked at other discussion related to this problem. Like, viewtopic.php?f=7&t=12707
Don't create a new thread for a problem that already exists!
User avatar
sohel
Guru
 
Posts: 859
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Why 673 WA?

Postby @mjad » Mon Nov 01, 2010 2:45 pm

AC
Last edited by @mjad on Thu Nov 04, 2010 3:09 am, edited 1 time in total.
@mjad
New poster
 
Posts: 44
Joined: Thu Jul 22, 2010 9:42 am

Re: 673 - Parentheses Balance

Postby sazzadcsedu » Wed Nov 03, 2010 7:29 pm

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.
sazzadcsedu
Experienced poster
 
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.

Re: 673 - Parentheses Balance

Postby @mjad » Thu Nov 04, 2010 3:11 am

:D Thanks for Help
i got AC
@mjad
New poster
 
Posts: 44
Joined: Thu Jul 22, 2010 9:42 am

Re: 673 - Parentheses Balance

Postby ujjal.ruet » Sun Jan 23, 2011 8:52 am

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.
ujjal.ruet
New poster
 
Posts: 15
Joined: Thu Sep 02, 2010 3:10 pm
Location: Dhaka,Bangladesh

Re: 673 - Parentheses Balance

Postby wawa » Mon Apr 04, 2011 4:05 pm

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...?????
wawa
New poster
 
Posts: 5
Joined: Thu Dec 16, 2010 8:17 am

Re: 673 - Parentheses Balance

Postby anik.bit0104 » Sun May 01, 2011 9:26 pm

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..
anik.bit0104
New poster
 
Posts: 6
Joined: Thu Sep 23, 2010 1:50 pm
Location: Dhaka, Bangladesh

Re: 673 - Parentheses Balance

Postby marjan » Tue Nov 01, 2011 11:57 am

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)
marjan
New poster
 
Posts: 3
Joined: Tue Nov 01, 2011 11:54 am

Re: 673 - Parentheses Balance

Postby cjahangir » Sat Dec 17, 2011 6:18 pm

#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.
cjahangir
New poster
 
Posts: 1
Joined: Fri Dec 09, 2011 8:27 pm

Re: 673 - Parentheses Balance

Postby brianfry713 » Tue Jan 10, 2012 1:06 am

cjahangir, check your code with an empty string for an input. Also use the code blocks when posting.
Check input and AC output for hundreds of problems on uDebug!
brianfry713
Guru
 
Posts: 5415
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 673 why RE???

Postby cse.mehedi » Sun Apr 01, 2012 3:05 am

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

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

PreviousNext

Return to Volume VI

Who is online

Users browsing this forum: No registered users and 1 guest