Write a C++ program that will create a trie data structure which can handle the

Question

Write a C++ program that will create a trie data structure which can handle the following text: "I like food". The user will enter the text. After you build the trie, allow the user to enter a single word and determine whether or not it was in the original text. You should provide 2 functions: (1) receive the text and build the trie; (2) receive a word and determine whether it exists within the text.

Do not use:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>

Explanation / Answer

Note: Internally string will converted to lower case for creating the trie.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <algorithm>

using name space std;

#define ARRAY_SIZE(a) size of(a)/size of(a[0])

// Alphabet size (# of symbols)
#define ALPHABET_SIZE (26)

// Convert key current character into index
// use only 'a' through 'z' and lowercase
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')

// trie node
struct Trie Node
{
struct Trie Node *children [ALPHABET_SIZE];
// is Leaf is true if the node represents
// end of a word
bool is Leaf;
};

// Returns new trie node (initialized to NULLs)
struct Trie Node *get Node(void)
{
struct Trie Node *pNode = NULL;

pNode = (struct Trie Node *)malloc (sizeo f(struct Trie Node));

if (pNode)
{
int i;

pNode->is Leaf = false;

for (i = 0; i < ALPHABET_SIZE; i++)
pNode->children[i] = NULL;
}

return p Node;
}

// If not present, inserts key into trie
// If the key is prefix of trie node, just marks leaf node
void insert(struct Trie Node *root, string key)
{
int level;
int length = key.length();
int index;

struct Trie Node *pCrawl = root;

for ( level =0; level < length; level++ )
{
inndex = CHAR_TO_INDEX (key [ level ]);
if ( !pCrawl -> children [index] )
pCrawl -> children [index] = get Node();
pCrawl = pCrawl ->children[index];
}
// mark last node as leaf
pCrawl->is Leaf = true;
}

// Returns true if key presents in trie, else false
bool search(struct Trie Node *root, string key)
{
int level;
int length = key.length();
int index;
struct Trie Node *pCrawl = root;
for (level = 0; level < length; level++)
{
index = CHAR_TO_INDEX(key[level]);

if (!pCrawl->children[index])
return false;

pCrawl = pCrawl->children[index];
}

return (pCrawl != NULL && pCrawl->isLeaf);
}

int main()
{
string data;
   string search word;
   string words[20];
char output[][32] = {"Not present in trie", "Present in trie"};
   int choice;
   int count=0,i=0;
  
struct Trie Node *root = get Node();
  
   while(1)
   {
       cout<<" Please Enter your choice 1.Build TRIE 2.Check for Presence of word in TRIE 3.Exit ";
       cin>>choice;
       cin.ignore();
       if(choice==3)
       {
           break;
       }
       else if(choice == 1)
       {
           cout<<"Please enter the sentence to be inserted"<<endl;
           get line(std::cin,data);
           std::transform(data.begin(), data.end(), data.begin(), ::tolower);
           string stream ssin(data);
           while (ssin.good() && count < 20)
           {
ssin >> words[count];
++count;
}
           for(i = 0;i<count; i++)
           {
               insert(root, words[i]);
           }      
       }
       else if(choice == 2)
       {
           cout<<"Enter the word to be searched: ";
           cin>>search word;
           std::transform(search_word.begin(), search_word.end(), search_word.begin(), ::tolower);
           cout<<search_word<<" is "<<output[search(root,search_word)];
       }
       else
       {
           cout<<"Wrong Choice ";
       }
   }  
return 0;
}

Output:

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.