INTRODUCTION

A trie is a tree structure well-suited to representing sets of strings. In a trie, letters are associated with linksbetween nodes---pointers---rather than with the nodes themselves.

A concordance is an alphabetical list of the words in a text with the frequencies of the words.

DESCRIPTION

Design, implement, test, and document a C++ program that reads an input file of text and builds a concordance of the words in the file. The program should also report the number of distinct words in the file. Represent the concordance with a trie. Words will be ordered alphabetically, disregarding capitalization. Implement this structure in a class.

The program should consider any sequence of letters to be a word, and all non-letter characters, including apostrophes, hyphens, and digits, are separators, equivalent to white space. One or more non-letters may separate words, and ends of lines separate words. Differences in capitalization do not make words different; that is, "HOUSE," "house," and "HouSe" are three instances of the same word. Words may be any length.

INPUT

The user enters the name of the input file from the terminal. Any file of text is legitimate input for this program.

OUTPUT

The program's output is a concordance of the words in the input file: a table of the words in alphabetical order accompanied by the number of times each word appears in the input text, as well as the number of distinct words in the text. The program prints this output to the terminal.

ERRORS

Since the program can process any input text file, it is not called on to detect any errors.

EXAMPLE

If an input file is this: This is a small test file, containing a small number of words. then the corresponding output might look something like this: Word Count --------------- A 2 CONTAINING 1 FILE 1 IS 1 NUMBER 1 OF 1 SMALL 2 TEST 1 THIS 1 WORDS 1 --------------- The file contains 10 distinct words.

OTHER REQUIREMENTS

Implement only these operations in the concordance class.

• A default constructor; initially the concordance is empty.
• A destructor.
• insert(word) Insert word in the concordance.
• length() Return the length of the invoking concordance/tree; that is, the number of distinct words in it.
• A function to print out the concordance in alphabetical order. You need not overload "

HINTS

When the insert() function is asked to insert a word that is already represented in the trie, the function increments the word's count. Note that this allows a simple main program: just read and insert every input word.

Printing the words represented in a trie will require a stack of characters. Include in the stack class a function that prints a stack's contents from the bottom up.

HAND IN

Include several tests of your program. Any file of text is good input.