112 - Tree Summing

[LlatzerandToni]

Try this:

Code: Select all

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

Code: Select all

no
no

[Tiramisu]

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

[darksk4]

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;}
};
Token lookahead;
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){}
      void addChild(Grammar *c){child.push_back(c);}
      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;
                return Token(RIGHTBRACE, lexeme);
             }
             else if(c == EOF)
                return Token(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);
                return Token(NUMBER, lexeme);
             }
             break;
          case 2:
             if(c == ')')
             {
                lexeme += c;
                return Token(EMPTY, lexeme);
             }
             else if(c == ' ' || c == '\n')
             {
                c = getchar();
             }
             else
             {
                ungetc(c, stdin);
                return Token(LEFTBRACE, lexeme);
             }
             break;
      }
   }
}


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

   if(lookahead.getValue() == expectedToken)
   {
      retrival = new Grammar(lookahead.getLex());
      lookahead = scan();
      return retrival;
   }
   else if(lookahead.getValue() == EOF)
   {
      return NULL;
   }
   else
   {
      return NULL;
   }
}
Grammar *expression();
Grammar *factor()
{
   Grammar *factorNode = new Grammar("factor");
   if(lookahead.getValue() == EOF)
      return factorNode;
   if(lookahead.getValue() == EMPTY)
      factorNode->addChild(match(EMPTY));
   else
   {
      factorNode->addChild(match(LEFTBRACE));
      factorNode->addChild(expression());
      factorNode->addChild(match(RIGHTBRACE));
   }
   return factorNode;
}
Grammar *expression()
{
   Grammar *expressionNode = new Grammar("expression");
   if(lookahead.getValue() == EOF)
      return expressionNode;
   expressionNode->addChild(match(NUMBER));
   expressionNode->addChild(factor());
   expressionNode->addChild(factor());
/*   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");
   if(lookahead.getValue() == EOF)
      return startNode;
   if(lookahead.getValue() == NUMBER)
   {
      startNode->addChild(match(NUMBER));
      if(lookahead.getValue() == EMPTY)
         startNode->addChild(match(EMPTY));
      else
      {
         startNode->addChild(match(LEFTBRACE));
         startNode->addChild(expression());
         startNode->addChild(match(RIGHTBRACE));
      }
   }
   else if(lookahead.getValue() == EMPTY)
   {
      startNode->addChild(match(EMPTY));
   }
   return startNode;
}
Grammar *parse()
{
   return start();
}

int main()
{
   Grammar *parseTree;
   lookahead = scan();
   while(lookahead.getValue() != EOF)
   {
//      std::cout << lookahead.getLex() << std::endl;
//      lookahead = scan();
      parseTree = parse();
//      print(parseTree, 0);
//      IntPrint(parseTree, 0);
      int target = atoi(parseTree->getChild(0)->getTitle().c_str());
      if(treeP(parseTree, 0, target) && parseTree->getChild(1)->getTitle() != "()")
        std::cout << "yes" << std::endl;
      else
        std::cout << "no" << std::endl;

   }
   return 0;
}