## 112 - Tree Summing

Moderator: Board moderators

LlatzerandToni
New poster
Posts: 15
Joined: Sun Apr 23, 2006 1:35 pm

### Re: 112 - Tree Summing

Try this:

Code: Select all

``````0 (1()())
0 (0(1()())(1()()))
``````

Code: Select all

``````no
no
``````
Lol

Tiramisu
New poster
Posts: 8
Joined: Fri Feb 20, 2015 10:28 am

### Re: 112 - Tree Summing

Thanks a lot, don't know why i was checking for sum=n outside the loop! now got accepted!!

darksk4
New poster
Posts: 13
Joined: Sun Jul 29, 2012 7:10 pm

### Re: 112 - Tree Summing

Hi, Why my code is WA? all of your input have the same output. hmmm.

Code: Select all

``````
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cctype>
#include<vector>

enum {NUMBER, LEFTBRACE, RIGHTBRACE, EMPTY};

class Token
{
int value;
std::string lex;
public :
Token() : value(-1), lex(""){}
Token(int v, std::string l) : value(v), lex(l){}
int getValue(){return value;}
std::string getLex(){return lex;}
};
class Node
{
int value;
Node* right;
Node* left;
public :
Node() : value(0){}
Node(int value) : value(0), right(NULL), left(NULL){}
Node(int value, Node *r, Node *l) : value(0), right(r), left(l){}
void set(int v)
{
value = v;
}
void setRight(Node *r)
{
right = r;
}
void setLeft(Node *l)
{
left = l;
}
};
class Grammar
{
std::string title;
std::vector<Grammar*>child;
Node *node;
public :
Grammar() : title(""){}
Grammar(std::string t) : title(t){}
Grammar(std::string t, Node *n) : title(t), node(n){}
Grammar *getChild(int n){return child[n];}
std::string getTitle(){return title;}
int getSize(){return child.size();}
Grammar* getData(int t){return child[t];}

};

void print(Grammar *root, int level)
{
if(root != NULL)
{
for(int counter = 0 ; counter < level ; counter++)
std::cout << "----|";
std::cout << root->getTitle() << std::endl;
for(int numberOfChild = 0 ; numberOfChild < root->getSize() ; numberOfChild++)
print(root->getData(numberOfChild), level + 1);
}
}

void IntPrint(Grammar *root, int level)
{
if(root != NULL)
{
if(root->getTitle() == "expression")
{
for(int counter = 0 ; counter < level ; counter++)
std::cout << "----|";
std::cout << root->getChild(0)->getTitle() << std::endl;
}
for(int numberOfChild = 0 ; numberOfChild < root->getSize() ; numberOfChild++)
IntPrint(root->getData(numberOfChild), level + 1);
}
}
bool treeP(Grammar *root, int sum, int target)
{
if(root != NULL)
{
if(root->getTitle() == "expression")
{
sum += atoi(root->getChild(0)->getTitle().c_str());
if(root->getChild(1)->getChild(0)->getTitle() == "()" && root->getChild(2)->getChild(0)->getTitle() == "()")
{
//            std::cout << "SUM : " << sum << " Target :  " << target << std::endl;
if(sum == target)
return true;
}

}

for(int numberOfChild = 0 ; numberOfChild < root->getSize() ; numberOfChild++)
{
if(treeP(root->getData(numberOfChild), sum, target))
return true;
}
}
}

Token scan()
{
int state = 0 ;
std::string lexeme = "";
char c = getchar();
while(true)
{
switch(state)
{
case 0:
if(isdigit(c) || c == '-')
{
lexeme += c;
c = getchar();
state = 1;
}
else if(c == '(')
{
lexeme += c;
c = getchar();
state = 2;
}
else if(c == ')')
{
lexeme += c;
}
else if(c == EOF)
else if(isspace(c))
{
c = getchar();
}
break;
case 1:
if(isdigit(c))
{
lexeme += c;
c = getchar();
}
else if(c == ' ' || c == '\n')
{
c = getchar();
}
else
{
ungetc(c, stdin);
}
break;
case 2:
if(c == ')')
{
lexeme += c;
}
else if(c == ' ' || c == '\n')
{
c = getchar();
}
else
{
ungetc(c, stdin);
}
break;
}
}
}

Grammar *match(int expectedToken)
{
Grammar *retrival = NULL;

{
return retrival;
}
{
return NULL;
}
else
{
return NULL;
}
}
Grammar *expression();
Grammar *factor()
{
Grammar *factorNode = new Grammar("factor");
return factorNode;
else
{
}
return factorNode;
}
Grammar *expression()
{
Grammar *expressionNode = new Grammar("expression");
return expressionNode;
/*   int value = atoi(expressionNode->getChild(0)->getTitle().c_str());
std:: cout << "Value : "  << value << std::endl;
std::cout << "LEFT : ";
if(expressionNode->getChild(1)->getSize() == 3)
{
std::cout << expressionNode->getChild(1)->getChild(1)->getChild(0)->getTitle();
}
std::cout << std::endl;
std::cout << "RIGHT : ";
if(expressionNode->getChild(2)->getSize() == 3)
{
std::cout<< expressionNode->getChild(2)->getChild(1)->getChild(0)->getTitle();
}
std::cout << std::endl;
*/

return expressionNode;
}
Grammar *start()
{
Grammar *startNode = new Grammar("Start");
return startNode;
{
else
{
}
}
{
}
return startNode;
}
Grammar *parse()
{
return start();
}

int main()
{
Grammar *parseTree;
{
//      std::cout << lookahead.getLex() << std::endl;