673 - Parentheses Balance

[vinocit]

Hai guys. I dont reply to any post but do keep in mind that empty string has to give out "Yes" . I did this mistake and was looking into it for 3 days

[anton_indrawan]

Help me, i don't know why i got WA, i already test my code with many input...

Code: Select all

 got AC .. code removed


[mf]

Here are a couple of examples where your program goes wrong:

Code: Select all

2
[]
(([())])

Your algorithm is too complex for such a simple problem. You only need a simple stack to solve it.

[anton_indrawan]

Hai mf, thank about your information..
I got AC with 0.050 seconds using the stack (include<stack>)

Is it necessary to create own class stack ?
Which one is faster, own class stack or using the lib one ?

Thx Before.. Sorry for my language

[mf]

Is it necessary to create own class stack ?

No. And why do you even ask? If you feel like writing your own stack, just do it, it's very simple:

Code: Select all

int stk[1000], top = 0;  // the stack

push an element x:  stk[top++] = x;
popping an element: stk[--top]

You see, the ops are so simple, you don't even need a class to hold them.

[poka]

Could anyone help me, i don't know why i got WA. Here is my code in java.


import java.io.*;
import java.util.*;

public class Main
{
public static boolean oklepaji(String niz)
{
Stack<Character> s = new Stack<Character>();
for (int i = 0; i < niz.length(); i++)
{
char znak = niz.charAt(i);
if (znak == '(' || znak == '[') s.push(znak);
else if (znak == ')' && !s.empty() && s.peek() == '(') s.pop();
else if (znak == ']' && !s.empty() && s.peek() == '[') s.pop();
else return false;
}
if (!s.empty()) return false;
return true;
}

public static void main(String[] args) throws IOException
{
BufferedReader vhod = new BufferedReader(new
InputStreamReader(System.in));

int n = Integer.parseInt(vhod.readLine());
String[] tab = new String[n];
for (int i = 0; i < n; i++)
{
tab[i] = vhod.readLine();
}
System.out.println();
for (int i = 0; i < n; i++)
{
if (oklepaji(tab[i])) System.out.println("Yes");
else System.out.println("No");
}
}
}

[mf]

Probably because you have an unnecessary System.out.println();

[mars kaseijin]

I went through problem description looking for sort and ordered in addition to balanced output. I found none, hence "([)]" should be Yes. Meaning the input can be jumbled as long as it balances in the end.

dont open a new thread as there is already many threads...think about that.
however ur program gives wrong output for this set of input.
input:

Code: Select all

7
([])
(([()])))
([()[]()])()
([)]
(
()(
[()


ur output is:

Code: Select all

Yes
No
Yes
Yes
No
No
No



My AC program gives:

Code: Select all

Yes
No
Yes
No
No
No
No



Hope it will help.

[anton_indrawan]

Hay mf
thx for your information, you are very experienced ... ^__^

[poka]

Thanks, my program was accepted, just one system.out.println() was wrong....

[abid_iut]

please help
I am getting WA but why
it passed all the input in the boards
here is the code:

Code: Select all

Removed


pls help

[Obaida]

See my PM. You will get a good solution.

[abid_iut]

Thanks for ur PM
I am trying in that way. BUT CAN U PLS CHECK MY GIVEN CODE AND TELL ME IS THERE ANY MISTAKE?
and about ur logic in pm
can u pls explain input according to ur PM :

([)]

it should be no.

[Obaida]

This is a special case,
([)]

here when you get any input "[" then you make a Boolean variable 1 and then if you get any ")" then break and no. But if you get "]" before ")" then make the Boolean variable to 0.

Is it clear???

[abid_iut]

Now what is the problem?
It is giving WA but i think It passes all input
here is the code:

Code: Select all

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

char fb[200],tb[200];

int main()
{
   char line[200]="";
   int i,j,n,k,flag,l,p,q,an;
   scanf("%d",&n);
   for(int it=0;it<n;it++){
      gets(line);
      if(line[0]==NULL){printf("Yes\n");continue;}
      k=0;l=0;flag=0;an=0;
      for(i=0;line[i];i++){
         if(line[i]==')' && fb[0]==NULL){flag=1;break;}
         if(line[i]==']' && tb[0]==NULL){flag=1;break;}
         if(line[i]=='(' && line[i+1]==']'){flag=1;break;}
         if(line[i]=='[' && line[i+1]==')'){flag=1;break;}
         if(line[i]=='('){
            fb[k]='(';k++;
            p=k;
         }
         if(line[i]=='['){
            tb[l]='[';l++;
            q=l;
         }
         if(line[i]==')'){
            fb[p-1]=NULL;
            p--;
            k=p;
         }
         if(line[i]==']'){
            tb[q-1]=NULL;
            q--;
            l=q;
         }
      }
      if(flag==1){printf("No\n");}
      else {
         for(i=0;line[i];i++){
            if(fb[i]==NULL && tb[i]==NULL)an=1;
            else {
               an=0;break;
            }
         }
         if(an==1)printf("Yes\n");
         else printf("No\n");
         for(i=0;line[i];i++)line[i]=NULL;
      }
   }
   return 0;
}


pls help