Question & Answer: Data Structures Problem: Use C++ LANGUAGE Use C++ LANGUAGE There is a real program developed by a computer company that reads…..

#include <string>
#include <fstream>
#include <iomanip> //for fomatting the output

using namespace std;

int instru = 1; //if instru is 1, tells the Print() printing the tree,if instr is 3,
//tells the print() printing the words which length is greater than 3.
int wordlen_3 = 0; //number of words which length is greater than 3.

class ItemType {
public:
ItemType() {
word = “”;
times = 1;
}

ItemType(string Word) {
word = Word;
}

bool operator == (const string &s) {
return (word == s);
}

bool operator < (const string &s) {
return (word.length() < s.length());
}

string word;
int times;
};

struct TreeNode
{
ItemType info;
TreeNode* left;
TreeNode* right;
};

template<class ItemType>
bool TreeType<ItemType>::IsFull()const
// Returns true if there is no room for another item
// on the free store; false otherwise.
{
TreeType* location;

try {
location = new TreeType;
delete location;
return false;
}
catch (bad_alloc exception) {
return true;
}
}

template<class ItemType>
bool TreeType<ItemType>::IsEmpty()const
// Return ture if the tree is empty, false otherwise
{
return (root == NULL);
}

int CountNodes(TreeNode* tree)
// Post: returns the number of nodes in the tree.
{
if (tree == NULL)
return 0;
else
return CountNodes(tree->left) +
CountNodes(tree->right) + 1;
}

void CountNodes_3(TreeNode* tree, int& count)
//counts the number of words which length is greater than 3
{
if (tree != NULL)
{
CountNodes_3(tree->left, count);
if (tree->info.word.length() > 3)
count++;
CountNodes_3(tree->right, count);
}
}

template<class ItemType>
int TreeType<ItemType>::Getlength()const
// Calls recursive function CountNodes to count the
// nodes in the tree.
{
//Calls recursive function CountNodes_3 counts the number of words which length is greater than 3
if (instru == 3)
{
CountNodes_3(root, wordlen_3);
int length = wordlen_3;
wordlen_3 = 0;
return length;
}
else
return CountNodes(root);
}

void RetrieveTree(TreeNode* tree, ItemType& item, bool& found)
// Recursively searches tree for item.
// Post: If there is an element someItem whose key matches item’s,
//       found is true and item is set to a copy of someItem;
//       otherwise found is false and item is unchanged.
{
if (tree == NULL)
found = false;
else if (item < tree->info.word)
RetrieveTree(tree->left, item, found);
else if (item == tree->info.word)
{
item = tree->info;
found = true;
}
else
RetrieveTree(tree->right, item, found);
}

void Insert(TreeNode*& tree, ItemType item)
// Inserts item into tree.
// Post: item is in tree; search property is maintained.
{
if (tree == NULL)
{
tree = new TreeNode;
tree->info = item;
tree->left = NULL;
tree->right = NULL;
}
else if (item < tree->info.word)
Insert(tree->left, item);
else
Insert(tree->right, item);
}

template<class ItemType>
void TreeType<ItemType>::PutItem(ItemType item)
// Calls recursive function Insert to insert item into tree.
{
Insert(root, item);
}

void GetPredecessor(TreeNode* tree, ItemType& data)
// Sets data to the info member of the right-most node in tree.
{
while (tree->right != NULL)
tree = tree->right;
data = tree->info;
}

void Delete(TreeNode*& tree, ItemType item);
void DeleteNode(TreeNode*& tree)
// Deletes the node pointed to by tree.
// Post: The user’s data in the node pointed to by tree is no
//       longer in the tree. If tree is a leaf node or has only
//       non-NULL child pointer the node pointed to by tree is
//       deleted; otherwise, the user’s data is replaced by its
//       logical predecessor and the predecessor’s node is deleted.
{
ItemType data;
TreeNode* tempPtr;

tempPtr = tree;
if (tree->left = NULL)
{
tree = tree->right;
delete tempPtr;
}
else if (tree->right = NULL)
{
tree = tree->left;
delete tempPtr;
}
else
{
GetPredecessor(tree->left, data);
tree->info = data;
Delete(tree->left, data);
}

}

void Delete(TreeNode*& tree, ItemType item)
// Deletes item from tree.
// Post: item is not in tree.
{
if (item < tree->info.word)
Delete(tree->left, item);
else if (item == tree->info.word)
DeleteNode(tree);
else
Delete(tree->right, item);
}

template<class ItemType>
void TreeType<ItemType>::DeleteItem(ItemType item)
// Calls recursive function Delete to delete item from tree.
{
Delete(root, item);
}

void PrintTree(TreeNode* tree, std::ofstream& outFile)
// Prints info member of items in tree in sorted order on outFile and screen
{
if (tree != NULL)
{
PrintTree(tree->left, outFile);
outFile << left << setw(15) << tree->info.word << right << setw(5) << tree->info.times << endl;
cout << left << setw(15) << tree->info.word << right << setw(5) << tree->info.times << endl;
PrintTree(tree->right, outFile);
}
}

template<class ItemType>
void TreeType<ItemType>::Print(std::ofstream& outFile)const
// Calls recursive function Print to print items in the tree.
{
PrintTree(root, outFile);
}

template<class ItemType>
TreeType<ItemType>::TreeType()
{
root = NULL;
}

void Destory(TreeNode*& tree)
// Post: tree is empty; nodes have been deallocated.
{
if (tree != NULL)
{
Destory(tree->left);
Destory(tree->right);
delete tree;
}
}

template<class ItemType>
TreeType<ItemType>::~TreeType()
// Calls recursive function Destroy to destroy the tree.
{
Destory(root);
}

template<class ItemType>
void TreeType<ItemType>::MakeEmpty()
// Calls recursive function Destroy to destroy the tree.
{
Destory(root);
}

void CopyTree(TreeNode*& copy, const TreeNode* originalTree)
// Post: copy is the root of a tree that is a duplicate
//       of originalTree.
{
if (originalTree == NULL)
copy == NULL;
else
{
copy = new TreeNode;
copy->info = originalTree->info;
copy->left = NULL;
copy->right = NULL;
CopyTree(copy->left, originalTree->left);
CopyTree(copy->right, originalTree->right);
}
}

template<class ItemType>
void TreeType<ItemType>::operator=(const TreeType& originalTree)
// Calls recursive function CopyTree to copy originalTree
// into root.
{
if (this == &originalTree)
return;
Destory(root);
CopyTree(root, originalTree.root);
}

template<class ItemType>
TreeType<ItemType>::TreeType(const TreeType& originalTree)
// Calls recursive function CopyTree to copy originalTree
// into root.
{
CopyTree(root, originalTree.root);
}

void PreOrder(TreeNode* tree, queue<ItemType> preQue)
// Post: preQue contains the tree items in preorder.
{
if (tree != NULL)
{
preQue.push(tree->info);
PreOrder(tree->left, preQue);
PreOrder(tree->right, preQue);
}
}

void InOrder(TreeNode* tree, queue<ItemType> inQue)
// Post: inQue contains the tree items in inorder.
{
if (tree != NULL)
{
InOrder(tree->left, inQue);
inQue.push(tree->info);
InOrder(tree->right, inQue);
}
}

void PostOrder(TreeNode* tree, queue<ItemType> postQue)
// Post: postQue contains the tree items in postorder.
{
if (tree != NULL)
{
PostOrder(tree->left, postQue);
PostOrder(tree->right, postQue);
postQue.push(tree->info);
}
}

template<class ItemType>
void TreeType<ItemType>::ResetTree(OrderType order)
// Calls function to create a queue of the tree elements in
// the desired order.
{
switch (order)
{
case PRE_ORDER:
PreOrder(root, preQue);
break;
case IN_ORDER:
InOrder(root, inQue);
break;
case POST_ORDER:
PostOrder(root, postQue);
break;
}
}

template<class ItemType>
ItemType TreeType<ItemType>::GetNextItem(OrderType order, bool& finished)
// Returns the next item in the desired order.
// Post: For the desired order, item is the next item in the queue.
//       If item is the last one in the queue, finished is true;
//       otherwise finished is false.
{
ItemType item;
finished = false;
switch (order)
{
case PRE_ORDER:
item = preQue.front();
if (preQue.empty())
finished = true;
break;
case IN_ORDER:
item = inQue.front();
if (inQue.empty())
finished = true;
break;
case POST_ORDER:
item = postQue.front();
if (postQue.empty())
finished = true;
break;
}
return item;
}

template<class ItemType>
ItemType TreeType<ItemType>::GetItem(ItemType item, bool& found)
// Recursively searches tree for item.
// Post: If there is an element someItem whose key matches item’s,
//       found is true and item is set to a copy of someItem;
//       otherwise found is false and item is unchanged.
{
TreeNode* location;
location = root;
found = false;
while (!found&&location != NULL)
{
if (item < location->info.word)
location = location->left;
else if (item == location->info.word)
{
location->info.times++;
item = location->info;
found = true;
}
else
location = location->right;
}
return item;
}

bool issentence(string& word) {
//if the string begin with ( , ” or ‘, we will erases it from the begin of the string.
if ((word[0] == ‘”‘) || (word[0] == ‘)’) || (word[0] == ”’))
word.erase(word.begin());
//if the string’s tail is lowercase word
if (word[word.length() – 1] > 96 && word[word.length() – 1] < 123)
return false;
//if the string’s tail is upcase word
else if (word[word.length() – 1] > 64 && word[word.length() – 1] < 91)
return false;
//if the string ends with periods, exclamation points, or question marks
else if (word[word.length() – 1] == ‘.’ || word[word.length() – 1] == ‘!’ || word[word.length() – 1] == ‘?’)
{
while (word[word.length() – 1] < 65 || word[word.length() – 1]>122 || (word[word.length() – 1] > 90 && word[word.length() – 1] < 97))
{
word.erase(word.length()-1);
}
return true;
}
//if the string’s tail is not alphabet
else {
while (word[word.length() – 1] < 65 || word[word.length() – 1]>122 || (word[word.length() – 1] > 90 && word[word.length() – 1] < 97))
{
word.erase(word.length() – 1);
}
return false;
}
}

void toLower(string& word)
//convert the alphabets in the word to lowercase
{
for (int i = 0; i < word.length(); i++)
{
if (word[i] < 91 && word[i]>64)     //convert upcase to lowercase
word[i] = word[i] + 32;
else if (word[i] < 58 && word[i]>47) //ignore the numbers in the string
{
word.erase(i);
i–;
}
}
}

void PrintSentence(queue<int> sentence,ofstream& outFile)
//print average sentence length to file outFile and screen
{
int wordsnum = 0;
int length = sentence.size();
while (!sentence.empty())
{
wordsnum += sentence.front();
sentence.pop();
}
outFile << “Average sentence length: ” << wordsnum / length << endl;
cout << “Average sentence length: ” << wordsnum / length << endl;
}

void TotalWords(int wordsnumber, ofstream& outFile)
//print total number of words to file outFile and screen
{
outFile << “Total number of words: ” << wordsnumber << endl;
cout << “Total number of words: ” << wordsnumber << endl;
}

void UniqueWords(TreeType<ItemType> tree, ofstream& outFile)
//print number of unique words to file outFile and screen
{
outFile << “Number of unique words: ” << tree.Getlength() << endl;
cout << “Number of unique words: ” << tree.Getlength() << endl;
}

void UniqueWords_3(TreeType<ItemType> tree, ofstream& outFile)
//print number of unique words of more than three letters to file outFile and screen
{
instru = 3;
outFile << “Number of unique words of more than three letters: ” << tree.Getlength() << endl;
cout << “Number of unique words of more than three letters: ” << tree.Getlength() << endl;
instru = 1;
}

void AverageWorLen(unsigned long int num, int length, ofstream& outFile)
//print average word length to file outFile and screen
{
outFile << “Average word length: ” << num/length << endl;
cout << “Average word length: ” << num / length << endl;
}

string getOutputNames(string inputfile)
//get the name of output file
{
size_t found = inputfile.find_last_of(‘.’);
inputfile.insert(found, “output”);
return inputfile;
}

void Statics(ifstream& in, ofstream& out)
{
string word; //the string each time get from cin
int i = 0;   //i is the length of one sentence
int numberWords = 0;   //whole number of words in the text
unsigned long int lengofword = 0; //total number of length of all of words
queue<int> sentence; //store the length of each sentence
TreeType<ItemType> Tree;   //store each word’s information
ItemType item;   //store the information of each word
bool found;   //true if found in the Tree, false otherwise
while (!in.eof())
{
in >> word;
i++;
numberWords++;
if (issentence(word))
{
sentence.push(i);
i = 0;
}
toLower(word);
lengofword += word.length();
item.word = word;
item = Tree.GetItem(item, found);
if (!found)
Tree.PutItem(item);
}
Tree.Print(out);
TotalWords(numberWords, out);
UniqueWords(Tree, out);
UniqueWords_3(Tree, out);
AverageWorLen(lengofword, numberWords, out);
PrintSentence(sentence, out);
}

int main() {
cout << “LEXICON AND TEXT ANALYSIS( 1.Analyse 2.Quit ): ” << endl;
while (1)
{
cout << “Please choose: “;
int choice;
cin >> choice;
string filename;
ifstream infile;
ofstream out;
switch (choice)
{
case 1:
cout << “input the name of the file: “;
cin >> filename;
infile.open(filename);
while (!infile)
{
cout << “file can’t open, please input again: “;
cin >> filename;
infile.open(filename);
}
out.open(getOutputNames(filename));
cout << “Output file is: ” << getOutputNames(filename) << endl;
Statics(infile, out);
break;
case 2:
exit(0);
break;
default:
cout << “wrong input, please enter again ” << endl;
break;
}
}
return 0;
}

TreeType.h

#include <iostream>
#include <queue>

using namespace std;

struct TreeNode;

//class ItemType;

enum OrderType{PRE_ORDER, IN_ORDER, POST_ORDER};

template<class ItemType>
class TreeType
{
public:
TreeType();
~TreeType();
TreeType(const TreeType& originalTree);
void operator=(const TreeType& originalTree);
void MakeEmpty();
bool IsEmpty()const;
bool IsFull()const;
int Getlength()const;
ItemType GetItem(ItemType item, bool& found);
void PutItem(ItemType item);
void DeleteItem(ItemType item);
void ResetTree(OrderType order);
ItemType GetNextItem(OrderType order, bool& finished);
void Print(std::ofstream& outFile)const;
private:
TreeNode* root;
queue<ItemType> preQue;
queue<ItemType> inQue;
queue<ItemType> postQue;
};

input.txt

and
there
hello
world