Recursively create a tree

c++ expression-trees recursion

Question

I am trying to recursively create an expression tree. Whenever this function receives other expression variables it runs perfectly fine. But whenever it receives an integer (or in this case a string that takes it to the else statement) it crashes my program.

     void buildExpressionTree (istream &ins, BinaryNode* p)
     {
         string buffer;

         //read in from file             
         while ((ins.peek()!='\n') && (ins >> buffer))
         {
             if(p == NULL && buffer == "*","/","+","-")
             {
                 p = new BinaryNode(buffer, NULL, NULL);
                 buildExpressionTree(ins,p->left);
                 buildExpressionTree(ins,p->right);
             }
             else 
             {
                 p = new BinaryNode(buffer, NULL, NULL);
             }
        }
      }

p is the root of the tree (which is null when passed to this function) and ins is an input file stream object.

1
0
10/9/2013 8:52:38 AM

Accepted Answer

Sorry to say that it doesn't run fine, there are multiple errors

Firstly

if(p == NULL && buffer == "*","/","+","-")

should be

if(buffer == "*" || buffer == "/" || buffer == "+" || buffer == "-")

The comma doesn't work how you are expecting it to.

Secondly if you want to build up your tree you should return a pointer from the function, not pass a pointer into the function. Like this

 BinaryNode* buildExpressionTree (istream &ins)
 {
     string buffer;

     //read in from file    
     BinaryNode* p = NULL;
     while ((ins.peek()!='\n') && (ins >> buffer))
     {
         if(buffer == "*" || buffer == "/" || buffer == "+" || buffer == "-")
         {
             p = new BinaryNode(buffer, NULL, NULL);
             p->left = buildExpressionTree(ins);
             p->right = buildExpressionTree(ins);
         }
         else 
         {
             p = new BinaryNode(buffer, NULL, NULL);
         }
    }
    return p;
}

This seems to be a very common misunderstanding of how pointers work when passed to a function. If you pass a pointer to a function you can use it to modify what is being pointed to in the calling function, you cannot use it to modify the pointer itself in the calling function.

1
10/9/2013 9:24:24 AM


Related Questions





Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow