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

Data Structures Problem:

Use C++ LANGUAGE

Use C++ LANGUAGE

There is a real program developed by a computer company that reads a report (running text), issues warnings on style, and partially corrects bad style. You are to write a simplified version of this program with the following features.

Statistics A statistical summary is prepared for each report processed with the following information:

total number of words in the report;

number of unique words;

number of unique words of more than three letters;

average word length, average sentence length; and

a listing of the special words with the number of times each was used in the report.

Style Warnings Issue a warning in the following cases:

• Word used too often: List each unique word of more than three letters if its usage is more than 5% of the total number of words of more than three letters.

Sentence length too long: Write a warning message if the average sentence length is greater than 10.

Words too big: Write a warning message if the average word length is greater than 5.

Run Summary At the end of the run the special words are written to the file with the number of times each was used during the run of the program.

Input

From the keyboard:

The name of the file containing the text to be analyzed

List of special words

From the file:

The report to be analyzed; ended by <eof>. Allow the user to continue with another file name or quit.

Output

1.

   

For each report being analyzed write the following information to a file. The name of the file
A listing of the file
The statistical summary of the report (See Statistics above.)

The style warnings given (See Style Warnings above.)

An alphabetical listing of the special words one per line with the number of times each was used throughout

2.
the run of the program.

Data Structures

A list to contain the special words

A list of unique words in the report, created as the file is read. If a word is not in the list, put it there. If it is,

increment a counter showing how many times the word has been used.

Definitions

Word: Sequence of letters ending in a blank, a period, an exclamation point, a question mark, a colon, a comma, a single quote, a double quote, or a semicolon. Numbers do not appear in the words; they may be ignored.

Unique word: Words that are spelled the same, ignoring uppercase and lowercase distinctions.
Sentence: Words between end of sentence markers or the beginning of the report and the first end of sentence marker.

Deliverables

 A listing of your program file including any included files

 A listing of your test plan as input to the program

 A listing of the output from your test run

Use C++ LANGUAGE

Use C++ LANGUAGE

#include “TreeType.h”

#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;
}
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)
{
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