673 - Parentheses Balance

[20717TZ]

673 Accepted but so long time. CPU=0:07.137 My God!!!!!
I think my algorithm is so simple and it should execute quickly, but I am wrong.
Why?
help me plzzzzzzz!

[cpp]
#include <stdio.h>
#include <string>
using namespace std;

int fnBalance(string s)
{
int place;

for(int i=0;s.find("[]")!=-1 || s.find("()")!=-1;i++)
{
while((place=s.find("[]"))!=-1)
s.erase(place,2);
while((place=s.find("()"))!=-1)
s.erase(place,2);
}
return s.length()==0?1:0;
}

void main()
{
FILE* fp=fopen("Input.txt","r");
int n; char c; string s;

fscanf(fp,"%d",&n);
c=fgetc(fp);//fgets(cs,MAX,fp);//skip a '\n'
for(int i=0;i<n;i++)
{
s="";//reset
while((c=fgetc(fp))!='\n' && c!=EOF)
s+=c;
printf("%s\n",fnBalance(s)?"Yes":"No");
}
}
[/cpp]

[Dominik Michniewski]

1. don't use STL - think how it can be done without string
2. don't post code, which is accepted - it's spoiler - anyone can submit it and get Accepted without any work - that's not fair. Please change code to description of used algorithm

Best regards
DM

[20717TZ]

Thank you
I am frustrated with STL
is it OK?
i think time is everything in a contest, STL can supply it to me.
but its efficiency.... I just don't konw....

[Mohammad Mahmudur Rahman]

Well, STL provides some important resources & good use of it should be done whenever appropriate. It eases the work (Surely you don't need to re-invent the wheel.) But again, as it is built on the object oriented structure, it's surely a bit slow. So, you really need not use STL components such as a string class which you could have easily done with some backdated though more efficient techniques such as the array based C string. In fact, you must understand which one is more important in a particular stage, efficiency or ease of coding.

[JaviGS]

I recently discovered accidentally that, in every input of the judge, any string that contains the substring "[]" is correct. Am I right? I think that if this is correct the judge should provide more extra input to avoid such lucky incidents as mine.
Regards
Javi

[tetuya]

I got Wrong Answer too.
my program work fine too.
did you find the cause of WA?

[cpp]
#include <iostream>
#include <string>
#include <cstdio>
#include <functional>
#include <algorithm>
using namespace std;
char buff[200];

void func() {
string str;
cin.getline(buff,50);
string::size_type st;
str = buff;
int end;

do {
end = 0;

st = str.find("[]",0);
if(st==string::npos) end++;
else str.erase(str.begin()+st,str.begin()+st+2);

st = str.find("()",0);
if(st==string::npos) end++;
else str.erase(str.begin()+st,str.begin()+st+2);

} while(end < 2);

if(str.length()==0) cout << "Yes" << endl;
else cout << "No" << endl;
}
int main() {

int n;
cin >> n;
cin.getline(buff,50);//ignore \n

while(n--) {
func();
}
}
[/cpp]

[tetuya]

I used stack and got AC.but, i cant figure out why my first program cant get AC.
thanx

[Ghust_omega]

Hiii htl, the bug in your code is check if the stack its empty after all the push and pops , i just add this in your code and give AC

[c]
Before :
if(error)
printf("No\n");
else
printf("Yes\n");

After :
if(error)
printf("No\n");
else
if(top == 0)

printf("Yes\n");
else
printf("No\n");[/c]
with this change you get AC
Hope it helps
Keep posting [/c]

[Ivo Sluganovic]

I am frustrated, I tried every possible input, but I still keep on getting WA.
Does anybody have a clue what is wrong with my code?
Is it something with the classes?
Please help!

[c]
I got AC!
[/c]

[Junayeed]

Try this input

Code: Select all

3 
) 
() 
)( 

Output

Code: Select all

No 
Yes 
No 

Hope this will help.

[Ivo Sluganovic]

Thanks Junayeed, but it works perfectly for your input.

Could you post more inputs?

Thanks!

[Junayeed]

Try this

Input

Code: Select all

([)] 
( 
()( 
[()

Output

Code: Select all

No
No
No
No

And another thing, be ware of string length. It should be at least 128

[Ivo Sluganovic]

I reallized where my mistake was!

In some inputs like "(((])", I would print NO two times!

Thanks anyway!

[.pandre.]

Hi
I've seen all post in this forum and tried every input people told albout and got the rigth output, but the judge keeps saying my answer is not correct.
Can anyone help me?

here is my code:

[java]
import java.io.*;

class Main{

public static void main(String args[]){

String s;

//read the number of inputs
int n = Integer.parseInt(ReadLn(25).trim());

//for each input
for(int x=0; x<n; x++) {

//read the string
s = ReadLn(135).trim();

//if the number of elements is odd
if (s.length() % 2 != 0)
System.out.println("No"); //then it's incorrect
else {

//go through all caracters from the string
for(int i=0;i<s.length()-1;i++) {

//if the sequences () or [] exist in the string
if((s.charAt(i)== '(' && s.charAt(i+1) == ')') ||
(s.charAt(i)== '[' && s.charAt(i+1) == ']')){

//remove them
s = s.substring(0,i) + s.substring(i+2);

//and start from the beggining
i=0;
}
}

if(s.equals("") || s.equals("()") || s.equals("[]"))
System.out.println("Yes");
else
System.out.println("No");
}
}
}

static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}
}[/java]

[Maniac]

hmmm, everything looks correct to me. Just some comments:
Have you tried the special case of empty lines as input? Maybe you should also exclude the '\r' character in the readline function? And doesn't s.substring(i+2) give an exception when applied at the end of the string s?