C++

Forum

 
program not counting properly

Stephaniei492 (79)
Someone please help me fix this!! I would greatly appreciate it. I tested my count funtion. So my count function is not working properly, it should return 5 because 5 words have prefix "tal," but it is giving me 10. It's counting blank nodes.

This is my main.cpp file
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
 int main()
{
    string word;
    cout<<"Enter a word"<<endl;
    cin >> word;

    string filename;
  
    Trie trie;
    trie.addDictionary (filename);
    string t("tal");
    cout<< trie.count (t)<<endl;

}



This is my implementation.cpp file
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
 Trie :: Trie (){
     TrieNode*node=new TrieNode();
     root=node;
     node->left=NULL;
     node->right=NULL;
}

bool Trie::addDictionary (string filename){
        fstream file("sae-sorted.dic", ios::in);
        string word;
 
        if(!file.is_open())

        {
                cout << "File not found!\n";
                return false;
        }
        
        while (file >> word)
        {
          *this += word;    
        }
        
        return true;
}

Trie& Trie::operator+= (const string & word){
         TrieNode * curr = root;
         for (int i = 0; i < word.length(); i++) {
            if (curr->left == NULL){
                 TrieNode*node=new TrieNode();
                 node -> data = word[i];
                 node->left = NULL;
                 node->right = NULL;
                 curr->left = node;
                 if (i==word.length()-1){
                  	node->end= true;
		  			node->w=word;
            	 }
                 else {
                   node->end=false;
                 }
				curr = curr->left;
             }
        	 else{
                 curr = curr->left;
         		 while (curr->data != word[i]) {
            		 if (curr->right == NULL){
                 		TrieNode*node=new TrieNode();
                 		node -> data = word[i];
                 		node->right = NULL;
                 		node->left = NULL;
                 		curr->right = node;
                		if (i==word.length()-1){
                  			node->end= true;
		  					node->w=word;
            			}
               			else {
                   			node->end=false;
            			}
					 }
               		 curr = curr->right;
               }
         	}
		}
        return *this;
}



int Trie::count (string prefix){
         TrieNode * curr = root;
         for (int i = 0; i < prefix.length(); i++) {
             if (curr-> left==NULL){
              	return 0;
             }
             curr = curr->left;
         	 while (curr->data != prefix[i]) {
           		if (curr-> right==NULL){
              		return 0;
             	}  
            	curr = curr->right;
    		 }
   		 }
         return count(curr);
}


int Trie::count (TrieNode *curr){
        if (curr==NULL){
             return 0;
        }
        else{
          if (curr->end==true){
             return count(curr->left) + count(curr->right) + 1;
          }
          else{
             return count(curr->left) + count(curr->right);
          }
        }
}

int Trie::count (char * prefix){
	  string str(prefix);
	  return count(str);
}
Rehan FASTian (168)
Header file, i.e. definition of class?
Last edited on
Stephaniei492 (79)
this is my struct.

1
2
3
4
5
6
7
 
struct TrieNode {
     int data;
     bool end;
     string w;
     TrieNode *left;
     TrieNode *right;
};
Last edited on
Rehan FASTian (168)
definition of class Trie?
Stephaniei492 (79)
1
2
3
4
5
6
7
8
9
10
11
 
class Trie {
public:
     TrieNode *root;

      Trie ();
	virtual bool           addDictionary (string filename);
	Trie&    operator+= (const string & word);
	virtual int            count (string prefix);
	virtual int            count (TrieNode *curr);
	virtual int            count (char * prefix);
};
Rehan FASTian (168)
In Trie& Trie::operator+= (const string & word)

You're doing node->w=word; twice, where as there is no w in the trie node you're accessing.
Stephaniei492 (79)
oh sorry I have string w in my struct.
Stephaniei492 (79)
Someone please help me!!!!!!!!!!!!!!!!
Bourgond Aries (415)
Have you fixed what Rehan FASTian mentioned?
Stephaniei492 (79)
Yes, I have string w in struct.
Topic archived. No new replies allowed.