C++ Programming Homework Help on Generic Binary Search Tree Project

• 26th May, 2022
• 15:15 PM

#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

int type = -1; // 0 for int, 1 for double, 2 for string
vector types;

// strip the spaces from both ends of the string
string strip(string& s){
    s = regex_replace(s, regex("^ +"), "");
    s = regex_replace(s, regex(" +$"), "");
    return s;
}

// split the line of string at the delimiter positions
vector split(string str, string delimiter = ","){
    vector res;
    size_t pos = 0;
    string token;
    while((pos = str.find(delimiter)) != string::npos){
        token = str.substr(0, pos);
        res.push_back(strip(token));
        str.erase(0, pos + delimiter.length());
    }
    res.push_back(strip(str));
    return res;
}

// read text from the standard input from the user
vector> read(string filename){
    vector> res;
    string str;
    ifstream in(filename);
    streambuf *cinbuf = cin.rdbuf();
    cin.rdbuf(in.rdbuf());
    while(getline(cin, str)){
        if(type == -1){
            if(isdigit(str[0])){
                if(str.find(".") != string::npos) type = 1;
                else type = 0;
            }
            else type = 2;
        }
        res.push_back(split(str));
        types.push_back(type);
        type = -1;
    }
    return res;
}

template
class TreeNode{
  public:
    T val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(T x) : val(x), left(NULL), right(NULL) {}
};

template
class BST{
    TreeNode* root = NULL;
    stack*> sta;
    
    TreeNode* insert(TreeNode* root, T key){
        TreeNode* newNode = new TreeNode(key);
        TreeNode* x = root;
        TreeNode* y = NULL;
        while(x){
            y = x;
            if(key < x->val) x = x->left;
            else x = x->right;
        }
        if(!y) y = newNode;
        else if(key < y->val) y->left = newNode;
        else y->right = newNode;
        return y;
    }
    
    public:
        BST(const vector& tokens){
            for(const auto& token : tokens){
                if(!root){
                    root = insert(root, token);
                }
                else{
                    insert(root, token);
                }
            }
        }
        
        void inOrder(){
            TreeNode* curr = root;
            while(curr || !sta.empty()){
                while(curr){
                    sta.push(curr);
                    curr = curr->left;
                }
                curr = sta.top(); sta.pop();
                cout << curr->val << " ";
                curr = curr->right;
            }
            cout << endl << endl;
        }
        
        void postOrder(TreeNode* node){
            if(!node) return;
            postOrder(node->left);
            postOrder(node->right);
            delete node;
        }
        
        void freeTree(){
            postOrder(root);
        }
};

int main(int argc, char *argv[]){

    vector> tokens = read(argv[1]);
    //for(auto token : tokens) cout << token << endl;
    for(int i=0; i         cout << "LINE - " << i << ":" << endl;
        type = types[i];
    if(type == 0){
        vector res;
        for(auto token : tokens[i]){
            try{
                res.push_back(stoi(token));
            }
            catch(exception& e){
                cout << "cannot convert " << token << " to int." << endl;
            }
        }
        BST* bst = new BST(res);
        bst->inOrder();
        bst->freeTree();
    }
    else if(type == 1){
        vector res;
        for(auto token : tokens[i]){
            try{
                res.push_back(stod(token));
            }
            catch(exception& e){
                cout << "cannot convert " << token << " to double." << endl;
            }
        }
        BST* bst = new BST(res);
        bst->inOrder();
        bst->freeTree();
    }
    else{
        BST* bst = new BST(tokens[i]);
        bst->inOrder();
        bst->freeTree();
    }
    }
    return 0;
}