0

I'm working on creating a BST of words provided in an input file. The input file I have is structure like so:

i apple
i bakery
i collapse

The i is a command that means the word following the command needs to be inserted into the BST. I am able to read and insert the words from an input file with 21 words, but I would like to load the words from an input file with up to 370,100 words. When I run my code on this input file it looks like the first line of the input file isn't even read but I am unable to figure out why.

class Node
{
    public:
        string word;
        Node *left, *right, *parent;

        Node() // default constructor
        {
            left = right = parent = NULL; 
        }

        Node(string to_insert) 
        {
            word = to_insert;
            left = right = parent = NULL; 
        }
};

class BST
{
    private:
        Node *root; 
    public:
        BST(); 
    void insert(string);
    void insert(Node*, Node*);
        
};

BST :: BST()
{
    root = NULL;
}

void BST :: insert(string word)
{
    Node *to_insert = new Node(word); 
    if (root == NULL) 
        root = to_insert; 
    else
        insert(root,to_insert); 
}

void BST :: insert(Node* start, Node* to_insert)
{
    if (start == NULL)
        return;
    if (to_insert->word <= start->word)
    {
        if(start->left == NULL)
        {
            start->left = to_insert; 
            to_insert->parent = start; 
            return;
        }
        else // need to make recursive call
        {
            insert(start->left, to_insert);
            return;
        }
    }
    else // inserted node has larger key, so go right
    {
        if(start->right == NULL)
        {
            start->right = to_insert; 
            to_insert->parent = start; 
            return;
        }
        else 
        {
            insert(start->right, to_insert);
            return;
        }
    }
}

int main(int argc, char** argv)
{
    if (argc < 3) // must provide two arguments as input
    {
        throw std::invalid_argument("Usage: ./treewrapper <INPUT FILE> <OUTPUT FILE>"); // throw error
    }

    ifstream input; // stream for input file
    ofstream output; // stream for output file

    input.open(argv[1]); // open input file
    output.open(argv[2]); // open output file

    string command; // to store the next command and operation
    char *com, *dummy, *valstr, *op; // for using with strtok, strtol
    string val = ""; // the value from the command

    BST myBST;

    int inserted = 0;

     while(getline(input,command))
    {
      cout << "Checking command" << "\n";
        if (command.length() == 0) // command is empty
            continue;
        com = strdup(command.c_str()); // annoying, first copy string into a "C-style" string
        op = strtok(com, " \t"); //tokenize command on whitespace, first token is operation

        valstr = strtok(NULL, " \t"); // next token is value, as string (check out documentation on strtok, to understand the parsing)
        cout << valstr << "\n";
        if(valstr != NULL) // first check if there is actually anything to convert into int
            val = valstr; // convert initial portion of valstr into an integer val, with base 10. Check out documentation on strtol for more details. 
        
    
        if(strcmp(op,"i") == 0) // insert into list
        {
            cout << "Insert "+ val << endl;
            myBST.insert(val);
            inserted++;
        }
     }
     cout << "Words inserted: " << to_string(inserted) << "\n";
     input.close();
     output.close();
}
first last
  • 21
  • 4
  • Just skimming through your code, I see something horrendous. You're using `strdup` so that you can tokenize with `strtok`, and leaking the memory. There's no need to use any string functions from C. Just put your command into a `istringstream` and read two strings from that. It handles whitespace for you. `string op, word; if (istringstream(command) >> op >> word) { if (op == "i" && !word.empty()) myBST.insert(word);` – paddy Nov 10 '22 at 04:42
  • I covered something very similar just yesterday in [this question](https://stackoverflow.com/questions/74368460) – Remy Lebeau Nov 10 '22 at 06:46

0 Answers0