How to Convert a Char Array to a Binary Tree using C++

Question

I have an assignment to convert a postfix expression from a txt document to a binary tree and then evaluate the expression. The base class was done for me, so I'm not going to include it in my code snippets. I am using and getline() to read the file line-by-line and assign each to a string variable to then pass to my derived class. The part I'm struggling with, however, is converting that string to a char array (as the assignment requires we do this) and then using that array to determine where to add each index value on the tree. I think the issue is that the text document is using numbers greater than 9 (for example: 35) and I don't know how to account for that in my code, so I keep getting segmentation fault errors. Anyway, I will post some code below and any help, explanations, or references would be much appreciated.

Main function:

int main() 
{
  ifstream inFile;
  ofstream outFile;
  string pfx;
  binaryExpressionTree tree;

  inFile.open("RpnData.txt");
  outFile.open("RpnDataOut.txt");

  do
  {
    tree.destroyTree();
    
    getline(inFile, pfx);

    tree.buildExpressionTree(pfx);

    outFile << tree.evaluateExpressionTree() << endl;
  }
  while (inFile);

}

The header file for my class:

#ifndef EXPRESSIONTREE_H
#define EXPRESSIONTREE_H

#include "binaryTree.h" 

class binaryExpressionTree : public binaryTreeType<string>
{
public:
  void buildExpressionTree(string);
  //Function to build the binary expression tree using a postfix string as a parameter
  //Precondition: Must read a string as a parameter
  //Postcondition: Will convert the string to a binary tree
  
  double evaluateExpressionTree();
  //Function to evaluate the expression tree
  //Postcondition: Recursively calls the private function to evaluate the expression tree

  bool search(const string&) const;
  //Function to search for a string in the tree
  //Precondition: Must have the address of a string to search for
  //Postcondition: Returns true if string is found in the tree and false otherwise

  void insert(const string&);
  //Function to insert a string at the end of a branch on the tree
  //Precondition: Must have the address of a string to insert
  //Postcondition: Inserts the string at the end of a branch

  void deleteNode(const string&);
  //Function to delete one node (containing the string provided as a parameter) of the tree
  //Precondition: Must have the address of a string to delete
  //Postcondition: Deletes the string from the tree

private:
  double evaluateExpressionTree(nodeType<string>*);
  //Private function to evaluate the expression tree
  //Precondition: Must have a pointer to a nodeType on the tree
  //Postcondition: Returns the value of the postfix expression
};

#endif

The code that produces the issue:

void binaryExpressionTree::buildExpressionTree(string pfxExpression)
{
  stack<nodeType<string>*> *tree;
  
  char* expression = new char[pfxExpression.length() +1];
  strcpy(expression, pfxExpression.c_str());

  for (int i = 0; i < pfxExpression.length(); i++)
  {
    if ((expression[i] >= 'a' && expression[i] <= 'z') || (expression[i] >= 'A' && expression[i] <= 'Z') || (expression[i] >= '0' && expression[i] <= '9'))
    {
      nodeType<string> *newNode;

      newNode = new nodeType<string>; //Create new node
      newNode->info = string(expression[i], expression[i+1]); //Set string of i to i+1 character in array to the info field 
      newNode->lLink = nullptr; //Make pointers for each branch nullptr
      newNode->rLink = nullptr;

      tree->push(newNode); //Push node onto the stack
//Through the use of cout statements, I have found that the error lies on the line above
    }//end if

The following are the expressions found in the text file:

35 27 + 3 *
23 30 15 * /
34 24 12 7 / * + 23 -
3 7 + 14 *

The following comes from the assignment directions themselves as an algorithm for the buildExpressionTree() member function. I apologize if the formatting is off, I tried to make it as readable as possible.

Here is the algorithm for building the expression tree:
 
Initialize a stack of pointers to binary tree nodes 

Get a postfix expression (this will be an input to the evaluateExpressionTree function)
// This line did not really make sense to me since evaluate() takes no parameters

Convert the string to a character array (include <cstring>)
// This is the wording that led me to believe we are supposed to convert it
//to a char array
 
For each token in the expression: 

   If token is a number: 

     Create a node 

     Convert the token from a character array to a string  

     Store the string in the info field   

     Push the new node onto the stack 

   else if token is an operator: 
  
     Create a node and store the operator in the info field 
  
     If stack is not empty: 

       Use top() to get a reference to the node at the top of the stack 

       Store the reference in the rLink field of the new node.  

       Use pop() to remove the node from the stack 

     If stack is not empty: 

         Use top() to get a reference to the node at the top of the stack 

         Store the reference in the lLink field of the new node 

         Use pop() to remove the node from the stack 

         Push the new node back onto the stack 

       else: 
         Error – Stack is empty 
     else: 
       Error – Stack is empty 
   else: 
     Error – unsupported token 

Get the next token
//This ends the for loop

if stack is not empty: 
   Pop the expression tree from the stack and store in root 

If stack is not empty: 
   There was an error, set root back to null

And finally, I will include the base class. It's a lot to dig through, and my professor did not separate the header and implementation files.

//Header File Binary Search Tree
#ifndef H_binaryTree
#define H_binaryTree

#include <iostream>

using namespace std;

//Definition of the Node
template <class elemType>
struct nodeType
{
    elemType info;
    nodeType<elemType> *lLink;
    nodeType<elemType> *rLink;
};

//Definition of the class
template <class elemType>
class binaryTreeType
{
protected:
    nodeType<elemType>  *root;


    
public:
    const binaryTreeType<elemType>& operator=
    (const binaryTreeType<elemType>&);
    //Overload the assignment operator.

    bool isEmpty() const;
    //Function to determine whether the binary tree is empty.
    //Postcondition: Returns true if the binary tree is empty;
    //               otherwise, returns false.

    void inorderTraversal() const;
    //Function to do an inorder traversal of the binary tree.
    //Postcondition: Nodes are printed in inorder sequence.

    void preorderTraversal() const;
    //Function to do a preorder traversal of the binary tree.
    //Postcondition: Nodes are printed in preorder sequence.

    void postorderTraversal() const;
    //Function to do a postorder traversal of the binary tree.
    //Postcondition: Nodes are printed in postorder sequence.

    int treeHeight() const;
    //Function to determine the height of a binary tree.
    //Postcondition: Returns the height of the binary tree.

    int treeNodeCount() const;
    //Function to determine the number of nodes in a
    //binary tree.
    //Postcondition: Returns the number of nodes in the
    //               binary tree.

    int treeLeavesCount() const;
    //Function to determine the number of leaves in a
    //binary tree.
    //Postcondition: Returns the number of leaves in the
    //               binary tree.

    void destroyTree();
    //Function to destroy the binary tree.
    //Postcondition: Memory space occupied by each node
    //               is deallocated.
    //               root = NULL;

    virtual bool search(const elemType& searchItem) const = 0;
    //Function to determine if searchItem is in the binary
    //tree.
    //Postcondition: Returns true if searchItem is found in
    //               the binary tree; otherwise, returns
    //               false.

    virtual void insert(const elemType& insertItem) = 0;
    //Function to insert insertItem in the binary tree.
    //Postcondition: If there is no node in the binary tree
    //               that has the same info as insertItem, a
    //               node with the info insertItem is created
    //               and inserted in the binary search tree.

    virtual void deleteNode(const elemType& deleteItem) = 0;
    //Function to delete deleteItem from the binary tree
    //Postcondition: If a node with the same info as
    //               deleteItem is found, it is deleted from
    //               the binary tree.
    //               If the binary tree is empty or
    //               deleteItem is not in the binary tree,
    //               an appropriate message is printed.

    binaryTreeType(const binaryTreeType<elemType>& otherTree);
    //Copy constructor

    binaryTreeType();
    //Default constructor

    ~binaryTreeType();
    //Destructor

private:
    void copyTree(nodeType<elemType>* &copiedTreeRoot,
                  nodeType<elemType>* otherTreeRoot);
    //Makes a copy of the binary tree to which
    //otherTreeRoot points.
    //Postcondition: The pointer copiedTreeRoot points to
    //               the root of the copied binary tree.

    void destroy(nodeType<elemType>* &p);
    //Function to destroy the binary tree to which p points.
    //Postcondition: Memory space occupied by each node, in
    //               the binary tree to which p points, is
    //               deallocated.
    //               p = NULL;

    void inorder(nodeType<elemType> *p) const;
    //Function to do an inorder traversal of the binary
    //tree to which p points.
    //Postcondition: Nodes of the binary tree, to which p
    //               points, are printed in inorder sequence.

    void preorder(nodeType<elemType> *p) const;
    //Function to do a preorder traversal of the binary
    //tree to which p points.
    //Postcondition: Nodes of the binary tree, to which p
    //               points, are printed in preorder
    //               sequence.

    void postorder(nodeType<elemType> *p) const;
    //Function to do a postorder traversal of the binary
    //tree to which p points.
    //Postcondition: Nodes of the binary tree, to which p
    //               points, are printed in postorder
    //               sequence.

    int height(nodeType<elemType> *p) const;
    //Function to determine the height of the binary tree
    //to which p points.
    //Postcondition: Height of the binary tree to which
    //               p points is returned.

    int max(int x, int y) const;
    //Function to determine the larger of x and y.
    //Postcondition: Returns the larger of x and y.

    int nodeCount(nodeType<elemType> *p) const;
    //Function to determine the number of nodes in
    //the binary tree to which p points.
    //Postcondition: The number of nodes in the binary
    //               tree to which p points is returned.

    int leavesCount(nodeType<elemType> *p) const;
    //Function to determine the number of leaves in
    //the binary tree to which p points
    //Postcondition: The number of leaves in the binary
    //               tree to which p points is returned.
};

//Definition of member functions

template <class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
    root = NULL;
}

template <class elemType>
bool binaryTreeType<elemType>::isEmpty() const
{
    return (root == NULL);
}

template <class elemType>
void binaryTreeType<elemType>::inorderTraversal() const
{
    inorder(root);
}

template <class elemType>
void binaryTreeType<elemType>::preorderTraversal() const
{
    preorder(root);
}

template <class elemType>
void binaryTreeType<elemType>::postorderTraversal() const
{
    postorder(root);
}

template <class elemType>
int binaryTreeType<elemType>::treeHeight() const
{
    return height(root);
}

template <class elemType>
int binaryTreeType<elemType>::treeNodeCount() const
{
    return nodeCount(root);
}

template <class elemType>
int binaryTreeType<elemType>::treeLeavesCount() const
{
    return leavesCount(root);
}

template <class elemType>
void  binaryTreeType<elemType>::copyTree
(nodeType<elemType>* &copiedTreeRoot,
 nodeType<elemType>* otherTreeRoot)
{
    if (otherTreeRoot == NULL)
        copiedTreeRoot = NULL;
    else
    {
        copiedTreeRoot = new nodeType<elemType>;
        copiedTreeRoot->info = otherTreeRoot->info;
        copyTree(copiedTreeRoot->lLink, otherTreeRoot->lLink);
        copyTree(copiedTreeRoot->rLink, otherTreeRoot->rLink);
    }
} //end copyTree

template <class elemType>
void binaryTreeType<elemType>::inorder
(nodeType<elemType> *p) const
{
    if (p != NULL)
    {
        inorder(p->lLink);
        cout << p->info << " ";
        inorder(p->rLink);
    }
}

template <class elemType>
void binaryTreeType<elemType>::preorder
(nodeType<elemType> *p) const
{
    if (p != NULL)
    {
        cout << p->info << " ";
        preorder(p->lLink);
        preorder(p->rLink);
    }
}

template <class elemType>
void binaryTreeType<elemType>::postorder
(nodeType<elemType> *p) const
{
    if (p != NULL)
    {
        postorder(p->lLink);
        postorder(p->rLink);
        cout << p->info << " ";
    }
}

//Overload the assignment operator
template <class elemType>
const binaryTreeType<elemType>& binaryTreeType<elemType>::
operator=(const binaryTreeType<elemType>& otherTree)
{
    if (this != &otherTree) //avoid self-copy
    {
        if (root != NULL)   //if the binary tree is not empty,
            //destroy the binary tree
            destroy(root);

        if (otherTree.root == NULL) //otherTree is empty
            root = NULL;
        else
            copyTree(root, otherTree.root);
    }//end else

    return *this;
}

template <class elemType>
void  binaryTreeType<elemType>::destroy(nodeType<elemType>* &p)
{
    if (p != NULL)
    {
        destroy(p->lLink);
        destroy(p->rLink);
        delete p;
        p = NULL;
    }
}

template <class elemType>
void  binaryTreeType<elemType>::destroyTree()
{
    destroy(root);
}

//copy constructor
template <class elemType>
binaryTreeType<elemType>::binaryTreeType
(const binaryTreeType<elemType>& otherTree)
{
    if (otherTree.root == NULL) //otherTree is empty
        root = NULL;
    else
        copyTree(root, otherTree.root);
}

//Destructor
template <class elemType>
binaryTreeType<elemType>::~binaryTreeType()
{
    destroy(root);
}

template<class elemType>
int binaryTreeType<elemType>::height
(nodeType<elemType> *p) const
{
    if (p == NULL)
        return 0;
    else
        return 1 + max(height(p->lLink), height(p->rLink));
}

template <class elemType>
int binaryTreeType<elemType>::max(int x, int y) const
{
    if (x >= y)
        return x;
    else
        return y;
}

template <class elemType>
int binaryTreeType<elemType>::nodeCount(nodeType<elemType> *p) const
{
    if (p == nullptr)
        return 0;
    else
        return 1 + nodeCount(p->lLink) + nodeCount(p->rLink);
}


template <class elemType>
int binaryTreeType<elemType>::leavesCount(nodeType<elemType> *p) const
{
    if (p->lLink != nullptr && p->rLink != nullptr)
        return 0 + leavesCount(p->lLink) + leavesCount(p->rLink);
    else
        return 1;
}

#endif

Answer 1

After hours of tinkering with my code (what felt like running into a wall over and over again) I stumbled on the solution. Though this solution may be exclusive to my own issue, I thought it would be better to post it in the off chance that someone needs it.

void binaryExpressionTree::buildExpressionTree(string pfxExpression)
{
  stack<nodeType<string>*> tree;
  
  char* expression = new char[pfxExpression.length() +1];
  strcpy(expression, pfxExpression.c_str());

  char delim[] = " ";
  char *token;
  double num;

  token = strtok(expression, delim);
  
  do
  {
    if (isdigit(token[0]))
    {
      nodeType<string> *newNode;

      newNode = new nodeType<string>; //Create new node
      newNode->info = string(token); //Convert token to string and assign to info field

      newNode->lLink = nullptr; //Make pointers for each branch nullptr
      newNode->rLink = nullptr;

      tree.push(newNode); //Push node onto the stack
    }//end if
    else if (token[0] == '+' || token[0] == '-' || token[0] == '*' || token[0] == '/')
    {
      nodeType<string> *newNode;

      newNode = new nodeType<string>; //Create new node
      newNode->info = string(token); //Set string of i to i+1 character in array to the info field 
      newNode->lLink = nullptr; //Make pointers for each branch nullptr
      newNode->rLink = nullptr;

      if (!tree.empty())
      {
        newNode->rLink = tree.top();

        tree.pop();

        if (!tree.empty())
        {
          newNode->lLink = tree.top();

          tree.pop();

          tree.push(newNode);
        }
        else
          cout << "Error - stack is empty; not enough operands." << endl;
      }// end if
      else
        cout << "Error - stack is empty; not enough operands." << endl;
    }//end else if
    else
      cout << "Error - unsupported token." << endl;
  }
  while ((token = strtok(NULL, delim)) != NULL);

   if (!tree.empty())
    {
      root = tree.top();
    
      tree.pop();
      if (!tree.empty())
      {
        root = nullptr;
        cout << "Error - stack not empty after popping; clearing the tree." << endl;
      } 
    }
}//end buildExpressionTree()

First, I went back through the directions and noticed something I hadn't before thanks to @user4581301. My professor had asked us to use strok to tokenize the character array. Even after changing the majority of my function code, my program still produced a segmentation fault error.

Next, I searched many posts on this site for similar questions and answers, but had little to no luck. I reread through the comments on my original post and noticed another user, @darcamo, had pointed out another issue as well. I was using the stack object, tree, as a pointer instead of an object of a stack of pointers. Once I removed the extra * before tree in stack<nodeType<string>*> *tree my code ran without issue, and was even outputting the correct evaluations from that function to the output file (thankfully, I'm not sure if I could have managed debugging another function tonight).

After all this, I just want to say thank you again to the users who pointed out the mistakes and suggested other solutions (even though I could not use them myself).