Advertisement
Guest User

C++ binary tree /entropy

a guest
May 9th, 2012
234
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.83 KB | None | 0 0
  1. #include <conio.h>  
  2. #include <iostream>
  3. #include <cctype>
  4. #include <string>
  5. #include <fstream>
  6. #include <math.h>
  7.     using namespace std;
  8.  
  9. #define MAX_LEN_FILE    256  
  10. #define M_LOG2E 1.44269504088896340736 //log2(e)  
  11.  
  12. inline long double log2(const long double x){  
  13.     return  log(x) * M_LOG2E;
  14. }
  15.  
  16. struct TreeNode
  17. {
  18.     string word;
  19.     int grade, count;
  20.     TreeNode *left;    
  21.     TreeNode *right;  
  22.  
  23.     TreeNode(string str, int g)
  24.     {
  25.         word = str;
  26.         grade = g;
  27.         count = 1;
  28.         left = NULL;
  29.         right = NULL;
  30.     }
  31. };
  32.  
  33. void Find(TreeNode *node, string str, int g)
  34. {
  35.     if (g == node->grade)
  36.     {
  37.         if (str == node->word)
  38.         {
  39.             // Yes, the item has been found in the root node.
  40.             node->count++;
  41.             return;
  42.         }
  43.     }
  44.     else if (g < node->grade) {
  45.         // If the item occurs, it must be in the left subtree.
  46.         if (node->left == NULL)
  47.         {
  48.             node->left = new TreeNode(str, g);
  49.             return;
  50.         }
  51.         else
  52.             return Find( node->left, str, g );
  53.     }
  54.     else {
  55.         // If the item occurs, it must be in the right subtree.
  56.         if (node->right == NULL)
  57.         {
  58.             node->right = new TreeNode(str, g);
  59.             return;
  60.         }
  61.         else
  62.         return Find( node->right, str, g );
  63.     }
  64. }
  65.  
  66. double ComputeEntropy(TreeNode *root, int count)
  67. {
  68.     double entropy = 0;
  69.  
  70.     entropy += (-log2(root->count/(double)count)) * root->count;
  71.  
  72.     if (root->left != NULL)
  73.         entropy += ComputeEntropy(root->left, count);
  74.  
  75.     if (root->right != NULL)
  76.         entropy += ComputeEntropy(root->right, count);
  77.  
  78.     return entropy;
  79. }
  80.  
  81. int main()
  82. {
  83.     TreeNode *root;
  84.     char name[MAX_LEN_FILE], temp;
  85.     bool first = true;
  86.     int wordsCount = 0;
  87.  
  88.     root = NULL;
  89.  
  90.     cout << "Zadejte cestu k souboru: ";
  91.     cin >> name;
  92.  
  93.     ifstream file;
  94.  
  95.     file.open (name, ifstream::in);
  96.  
  97.     if(!file.is_open())
  98.     {
  99.         cout << "Spatne zadana cesta k souboru!" << endl;
  100.         getche();
  101.         return 0;
  102.     }
  103.  
  104.     int grade = 0;
  105.     string word;
  106.  
  107.     while (file.get(temp) && !file.eof())
  108.     {
  109.        
  110.         if(isalpha(temp))
  111.         {
  112.             word += temp;
  113.             grade += temp;
  114.         }
  115.         else if (word != "")
  116.         {
  117.             if (first)
  118.             {
  119.                 root = new TreeNode(word, grade);
  120.                 first = false;
  121.             }
  122.             else
  123.             {
  124.                 Find(root, word, grade);
  125.             }
  126.  
  127.             wordsCount++;
  128.             grade = 0;
  129.             word = "";
  130.         }
  131.     }
  132.  
  133.     file.close();
  134.  
  135.     cout.precision(10); // ??
  136.     cout << fixed << ComputeEntropy(root, wordsCount);
  137.  
  138.     getche();
  139.     return 0;
  140. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement