112 - Tree Summing

[minskcity]

I need test samples as well - my solution works on OJ's samples, but I still get WA.

[mrtamtam]

[c]
#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main()
{

int targetsum,neg,num,sum,level,empty,ans,i;
int stack[1024*1024];
char ch,oldch;

for (i=0; i< 1024*1024; i++)
stack = 0;

while (scanf("%d",&targetsum) > 0)
{
level = 0;
neg = 0;
num = 0;
empty = 0;
ans = 0;
oldch = '\0';

do
{
do
{
scanf("%c",&ch);
}
while ( (!isdigit( (int) ch)) && (ch != '-') && (ch != '(') && (ch != ')') );


if (isdigit( (int) ch))
{
num *= 10;
if (neg)
num -= ch - '0';
else
num += ch - '0';
empty = 0;
}
else
if (ch == '-')
{
neg = 1;
empty = 0;
}
else
if (ch == '(')
{
level++;

if (isdigit( (int) oldch ))
{
stack[level] = num;
num = 0;
neg = 0;
empty = 0;
}
}
else
if (ch == ')')
{
level--;
if (oldch == '(') empty++;

if (empty >= 2)
{
/* reach the root now */
sum = 0;
for (i=2; i<= 1+level; i++)
{
sum += stack;
/*
printf("%d ",stack);
*/
}

if (sum == targetsum)
ans = 1;
/*
printf("= %d\n",sum);
*/
empty = 0;
}

}

oldch = ch;

}
while ((level > 0));

if (ans)
printf("yes\n");
else
printf("no\n");

}

return 0;
}
[/c]

Negative input is checked
0 () -> No
0 (0 ()()) -> Yes

I can't find any Problem of this.
Please help.
Thanks..........

[mrtamtam]

[c]
#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main()
{

int targetsum,neg,num,sum,level,empty,ans,i;
int stack[1024*1024];
char ch,oldch;

for (i=0; i< 1024*1024; i++)
stack = 0;

while (scanf("%d",&targetsum) > 0)
{
level = 0;
neg = 0;
num = 0;
empty = 0;
ans = 0;
oldch = '\0';

do
{
do
{
scanf("%c",&ch);
}
while ( (!isdigit( (int) ch)) && (ch != '-') && (ch != '(') && (ch != ')') );


if (isdigit( (int) ch))
{
num *= 10;
if (neg)
num -= ch - '0';
else
num += ch - '0';
empty = 0;
}
else
if (ch == '-')
{
neg = 1;
empty = 0;
}
else
if (ch == '(')
{
level++;

if (isdigit( (int) oldch ))
{
stack[level] = num;
num = 0;
neg = 0;
empty = 0;
}
}
else
if (ch == ')')
{
level--;
if (oldch == '(') empty++;

if (empty >= 2)
{
/* reach the root now */
sum = 0;
for (i=2; i<= 1+level; i++)
{
sum += stack;
/*
printf("%d ",stack);
*/
}

if (sum == targetsum)
ans = 1;
/*
printf("= %d\n",sum);
*/
empty = 0;
}

}

oldch = ch;

}
while ((level > 0));

if (ans)
printf("yes\n");
else
printf("no\n");

}

return 0;
}
[/c]

Negative input is checked
0 () -> No
0 (0 ()()) -> Yes

I can't find any Problem of this.
Please help.
Thanks..........

[lu shukai]

i have tried more than thousand times and got wa again and again
here is my code

#include <iostream>
using namespace std;

struct BTreeNode
{
int value;
BTreeNode* lch;
BTreeNode* rch;
};

int sum;
char ch;
BTreeNode* root;
bool found;
bool ckn;

int getValue()
{
bool flag = true;
int ret = 0;
cin >> ch;
while (ch!='('&&ch!=')')
{
if (ch=='-')
flag = false;
if (ch>='0'&&ch<='9'){
ret = ret*10 + ch - '0';
ckn = true;
}
cin >> ch;
}
if (flag)
return ret;
else
return -ret;
}

void plantTree(BTreeNode* p)
{
ckn = false;
int v = getValue();
if (v == 0&&!ckn){
p->value = 0;
p->lch = NULL;
p->rch = NULL;
}
else
{
ckn = false;
p->value = v;
p->lch = new BTreeNode();
plantTree(p->lch);
cin >> ch;
while (ch!='(')
cin >> ch;
p->rch = new BTreeNode();
plantTree(p->rch);
}
}

void deleteTree(BTreeNode* p)
{
if (p!=NULL){
deleteTree(p->lch);
deleteTree(p->rch);
delete p;
}
}

bool getSum()
{
sum = 0;
bool flag = true;
while (cin>>ch)
{
if (ch == '-')
flag = false;
if (ch=='('){
if (!flag)
sum = -sum;
return true;
}
if (ch>='0'&&ch<='9')
sum=sum*10+ch-'0';
}
return false;
}

void addSum(BTreeNode* p,int current)
{
current+=p->value;
if(p->lch == NULL&&p->rch == NULL)
{
if (current == sum)
found = true;
}
if (p->lch!=NULL)
addSum(p->lch,current);
if (p->rch!=NULL)
addSum(p->rch,current);
}

int main()
{

while(getSum())
{
found = false;
root = new BTreeNode();
plantTree(root);
if (root->lch == NULL&&root->rch == NULL&&sum==0)
cout << "no\n";
else{
addSum(root,0);
if (found)
cout <<"yes\n";
else
cout <<"no\n";
}
deleteTree(root);
}
return 0;
}

please tell me what's wrong .
thx.

[hank]

0 () is false
77 (77(1()())()) is false

[hank]

0 () is false
77 (77(1()())()) is false

[hts]

I found the problem on my solution.
It wasn't processing correctly negative numbers

A little modification made my solution be accepted

c == '-'

Code: Select all

int      aceitavel(char c) 
{ 
   if(c == '(' || c == ')' || c == '-') 
      return 1; 
   else 
   if(c <= '9' && c >= '0') 
      return 1; 
   else 
      return 0; 
}

[minskcity]

Thanks a lot, now I got AC on this problem too - My program had the same mistake.
I usualy use cin >> int, so I do not need to worry about negative numbers but for this problem it does not work.

[ezra]

[c]
#include<stdio.h>
#include<stdlib.h>

void main()
{
long test;
char buff[1000];
char list[10000];
char temp[100];
long trave;
long temp2[10000];
int tree,find;
long left,right;
long i,j,k;
while(scanf("%d",&test)==1)
{
left=0;
right=0;
j=0;
do
{
gets(buff);
for(i=1;buff!=NULL;i++)
{
if(buff=='(')
left=left+1;
if(buff==')')
right=right+1;
if((int)buff!=32&&buff!='\n')
{
list[j]=buff;
j=j+1;
}
}
}
while(left!=right);
list[j]=NULL;

k=0;
find=0;
trave=0;
temp2[0]=0;
tree=0;
for(i=0;list!=NULL&&find==0;i++)
{
if(list!='('&&list!=')')
{
for(j=0;list!='('&&list[i]!=')';i++)
{
temp[j]=list[i];
j=j+1;
}
k=k+1;
temp[j]=NULL;
temp2[k]= atoi(temp);
trave=trave+temp2[k];
tree=1;
i=i-1;
}
else
{
if(list[i]=='('&&list[i+1]==')'&&list[i+2]=='('&&list[i+3]==')'&&tree==1)
{
i=i+3;
if(test==trave)
find=1;
}
else
{
if(list[i]==')')
{
trave=trave-temp2[k];
k=k-1;
}
}
}
}

if(find)
printf("yes\n");
else
printf("no\n");
}
}
[/c]

please anyone tell what is wrong with my code or perhaps my algo.
i keep getting WA on this altough i already check my possibilities.

isn't the answer for
0 ( () () )
no

is there any tricky input ?

[Hisoka]

hello, [D.3]Sadako.......

try with negatif input.

GOOD LUCK........

[ezra]

already tried it,and get proper result.
Or could you give me some posible negative input and the answer that could be tricky for me?

BTW,thanks [D.3] Ch0p1n

[Hisoka]

hello again........

this is some test case for you ;

Code: Select all

-7 (1 (-6 (2 (1 ()()) (-4 ()(1 (1 ()())(-1 ()())
   ) ) )  
   () ) () )
yes

0 ( )
no

3 (3 (4 (5 ()()) (8 (-3 (-7 ()())())(-4 ()(-8 ()()))))
     (6 (6 (-5 ()())(-6 ()(-9 ()())))(7 ()())))
yes

0 (1()
    (-2 () (1()())))
yes

1 (1 () (0 ()()) )
yes

- [*D.3*]Chopin -
_____________________________________________________________
SMISH is the best ?!?!?!?!??????????

[ezra]

gotcha!!!
I finally found what's the mistakes.
1. I made mistake convert the sequence expression on 1 line (buff) to the
list. I convert from index 1 which should be begun with 0.
**for(i=1;
2. the mistake is not the negative input but the traverse algo. I didnt
consider about the node which have no left child and only have right
child. Your sample realize me about that.

Finally thanks a million for your help because without your sample i never could find the bug of my code.
Thanks, [D.3] chopin


SMIHS always be the best!!!!!

[ezra]

please tell me the way to change the directory/drive where C program read/write a file.
with this code : fopen("a.txt","r"); the program will read the file a.txt from directory : c:\bc31\bin. how can i switch that?
Million thanks for helping.

[Hisoka]

Code: Select all

FILE *in;
in=fopen("C:/bc31/bin/a.txt","r");

why you want to do this ?