## 112 - Tree Summing

Moderator: Board moderators

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
I need test samples as well - my solution works on OJ's samples, but I still get WA. mrtamtam
New poster
Posts: 5
Joined: Wed Jan 15, 2003 9:50 pm

### 112 WA

[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.
Thanks.......... mrtamtam
New poster
Posts: 5
Joined: Wed Jan 15, 2003 9:50 pm

### 112 WA

[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.
Thanks.......... lu shukai
New poster
Posts: 7
Joined: Tue Aug 06, 2002 9:26 am

### p112 who can help me

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

{
current+=p->value;
if(p->lch == NULL&&p->rch == NULL)
{
if (current == sum)
found = true;
}
if (p->lch!=NULL)
if (p->rch!=NULL)
}

int main()
{

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

please tell me what's wrong .
thx.

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
0 () is false
77 (77(1()())()) is false

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
0 () is false
77 (77(1()())()) is false hts
New poster
Posts: 8
Joined: Sat Feb 22, 2003 2:56 am

### Re: Test cases for 112 (Tree Summing)?

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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
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
New poster
Posts: 31
Joined: Thu Nov 21, 2002 2:11 pm

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

void main()
{
long test;
char buff;
char list;
char temp;
long trave;
long temp2;
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;
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.

0 ( () () )
no

is there any tricky input ?

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

try with negatif input.

GOOD LUCK........ ezra
New poster
Posts: 31
Joined: Thu Nov 21, 2002 2:11 pm
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
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
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 ?!?!?!?!??????????  Last edited by Hisoka on Fri May 09, 2003 5:28 pm, edited 1 time in total.

ezra
New poster
Posts: 31
Joined: Thu Nov 21, 2002 2:11 pm
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
New poster
Posts: 31
Joined: Thu Nov 21, 2002 2:11 pm
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
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Code: Select all

``````FILE *in;
in=fopen("C:/bc31/bin/a.txt","r");``````
why you want to do this ? 