Recursively create a tree

c++ expression-trees recursion

Question

I'm attempting to build an expression tree recursively. This method works flawlessly whenever it is given more expression variables. However, it always crashes my application anytime it gets an integer (or in this instance, a text that directs it to the else statement).

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

Ins is an input file stream object, and p is the tree's root (which is null when supplied to this method).

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

Accepted Answer

I'm sorry to report that it doesn't operate well; there are many issues.

Firstly

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

ought to be

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

The comma doesn't function the way you would expect it to.

Second, you should return a pointer from the method rather than give a pointer into it if you want to build up your tree. like as

 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 widespread misconception about how pointers operate when provided to a function. You can only edit what is being highlighted in the calling function if you supply a reference to a function; you cannot modify the actual pointer 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