Description
This Assignment involves developing a ictionary that uses a Binary Search Tree (BST). This BST will be implemented represented with linked nodes, and will support operations including: inserting new word-meaning pairs into the dictionary, looking up the meaning of a particular word, and retrieving a list of all words in the dictionary.
OBJECTIVES AND GRADING CRITERIA
The main goals of this assignment include: implementing common BST operations, and making use of this BST in an application. You will also get practice implementing recursive methods to perform these common BST operations.
25 points
5 zyBooks Tests: automated grading test results are visible upon submission, and allow multiple opportunities to correct the organization and functionality of your code. Your highest scoring submission prior to the deadline will be recorded.
25 points
5 Hidden Tests: automated grading tests are run after the assignment’s deadline. They check for similar functionality and organizational correctness as the zyBooks Tests. But you will NOT be able to resubmit corrections for extra points, and should therefore consider and test your own code even more thoroughly.
GETTING STARTED
LECTURE NOTES
0. Create a new ava8 project in Eclipse. You can name this project whatever you like, but ictionary is a descriptive choice.
TE DICTIONARY
1. Add a new class called ictionary to your project. This class will make use of the efinitionNode class described in the next step. We are introducing this class first, to help you understand the context in which the efinitionNode’s helper methods will be used. This class must contain the private fields and publicly accessible methods shown in the following:
You may add additional private methods to help organize your implementation of these functions, but may not add additional fields or public methods. However most of the functionality for these methods will come from the efinitionNode’s recursive helper methods specified below.
TE DEFINITION NODE
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
private private efinitionode root; // the root definition in the BST / Inserts a new word along with its meaning into the dictionary. param word The word to be inserted param meaning The meaning of the word being inserted throws IllegalArgumentEception when the word is already in this dictionary / public public void void insert(String String word word, String String meaning) throws IllegalArgumentEception { // implement using the efinitionode’s insertelper() method } / Searches for the definition of a word, and then return that word’s meaning. param word The word that is being searched for return The meaning of the word, or null if the word cannot be found. / public public String String looup(String String word word) { // implement using the efinitionode’s looupelper() method } / Computes the number of words that are currently in this dictionary. return That number of words / public public int int getordCount() { // implement using the efinitionode’s getordCountelper() method } / Computes a list of all of the words that are currently in this dictionary. return That list of all the words / public public ArrayList 2. Create a new class called efinitionNode. Objects of this type will be used to represent the definitions (i.e. word and meaning pairs) in your dictionary. This class must contain the private fields and publicly accessible constructor/methods shown in the following:
You may add additional private methods to help organize your implementation of these functions, but may not add additional fields or public methods. After implementing these methods, you should revisit you ictionary class. Make use of these recursive helper methods to implement the methods within your ictionary class.
TE DRIVER APPLICATION
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
private private final final String String word word;// the word this definition defines private private final final String String meaning; // the meaning of that word private private efinitionode leftChild; // nodes preceding this one alphabetically private private efinitionode rightChild;// nodes following this one alphabetically / Constructs a efinitionode with the specified word and meaning. param word The word associated with this definition param meaning The meaning of that word throws IllegalArgumentEception when the word or meaning are either references to an empty string or null references. / public public efinitionode(String String word word, String String meaning) { } / This helper method inserts a new node into the tree or subtree that is rooted at this node.If it cannot directly add the new node as a child of this node, then it must recursively call this method on its appropriate child, to eventually complete this insertion. param newode The new node that is being inserted into the tree throws IllegalArgumentEception when the word inside newode is already in the tree.ultiple definitions for the same word are not allowed. / public public void void insertelper(efinitionode newode) throws IllegalArgumentEception { } / This helper method retrieves the meaning of a particular word from the tree or subtree rooted at this node.Lie the insertelper method above, this method should also be defined recursively. param word The word associated with the meaning being looed up return The meaning of that word, or null if the word is not found / public public String String looupelper(String String word word) { return return null null; } / This recursive helper method retrieves the number of words in the tree or subtree rooted at this node. return The number of definitions in this tree or subtree / public public int int getordCountelper() { return return 0; } / This recursive helper method retrieves a list containing all of the words in the tree or subtree rooted at this node. return The list of all words in this words tree or subtree / public public ArrayList 3. Your last job for this assignment is to develop a driver application to make use of your ictionary. Create a new class called Main to a new file called Main.java, and implement this driver within the main() method of that new class. This driver should continuously prompt the user to enter one command at a time, and process each of them until the user enters a ’ command to quit the program. For each of the command, you basically just need to call the corresponding method on a single ictionary object. The commands (which should be case insensitive) are as follows:
Command Corresponding Method
Description
I word meaning
insert(word, meaning)
“I” inserts a definition in the dictionary. It prints NIN: failed to insert duplicate word: word. for duplicate entry
L word lookup(word) “L” searches the definition of the word in the dictionary. It prints No definition found for the word word when a word doesn’t exist in the dictionary or There are no definitions in this empty dictionary. when the dictionary is empty.
A getAllWords() “A” gets all the words in the dictionary in sorted order, and then prints those words on a single line separated by spaces. Prints ictionary is empty. when the dictionary has no words.
C getWordCount() “C” gets the count of words in the dictionary.
“” quits the program
Some clarifications about the commands:
Your program should support commands in both lowercase and uppercase.
You may assume that for each command option entered, the number and format of arguments followed are always valid. E.g., an I’ (insert) command option won’t be followed by less than two arguments, and all the arguments can always be interpreted as strings separated by a single space. For the I’ (insert) command option, the first argument will be the word and the second argument will begin after the first argument and will continue till the end of the input line. When the user enters a command option not listed above, you should show user the warning message NIN: nrecognied command., and then re-prompt the user to enter another command. Whenever you show the user a warning message, you should not perform the corresponding operation on the dictionary, nor should you exit the program. Instead, you should reprompt the user, and continue the program until the user enters a q’. 4. Here is an interactive log that demonstrates using the complete application (the user’s input is displayed in a orange and the output is in black): ==================Dictionary ================= Enter ‘I’ to Insert a definition in the dictionary Enter ‘L’ to Lookup a definition in the dictionary Enter ‘A’ to print All the words in the dictionary Enter ‘C’ to print the Count of all words in the dictionary Enter ‘Q’ to quit the program =========================================== Please enter your command: i eccentric unconventional and slightly strange
==================Dictionary ================= Enter ‘I’ to Insert a definition in the dictionary Enter ‘L’ to Lookup a definition in the dictionary Enter ‘A’ to print All the words in the dictionary Enter ‘C’ to print the Count of all words in the dictionary Enter ‘Q’ to quit the program =========================================== Please enter your command: i accustom be used to
==================Dictionary ================= Enter ‘I’ to Insert a definition in the dictionary Enter ‘L’ to Lookup a definition in the dictionary Enter ‘A’ to print All the words in the dictionary Enter ‘C’ to print the Count of all words in the dictionary Enter ‘Q’ to quit the program =========================================== Please enter your command: i boring not interesting
==================Dictionary ================= Enter ‘I’ to Insert a definition in the dictionary Enter ‘L’ to Lookup a definition in the dictionary Enter ‘A’ to print All the words in the dictionary
5. Congratulations on finishing this CS300 assignment! After verifying that your work is correct, and written clearly in a style that is consistent with the course style guide, you should submit your
Enter ‘C’ to print the Count of all words in the dictionary Enter ‘Q’ to quit the program =========================================== Please enter your command: L boring
boring – not interesting
==================Dictionary ================= Enter ‘I’ to Insert a definition in the dictionary Enter ‘L’ to Lookup a definition in the dictionary Enter ‘A’ to print All the words in the dictionary Enter ‘C’ to print the Count of all words in the dictionary Enter ‘Q’ to quit the program =========================================== Please enter your command: i flight the action or process of flying through the air
==================Dictionary ================= Enter ‘I’ to Insert a definition in the dictionary Enter ‘L’ to Lookup a definition in the dictionary Enter ‘A’ to print All the words in the dictionary Enter ‘C’ to print the Count of all words in the dictionary Enter ‘Q’ to quit the program =========================================== Please enter your command: a
accustom, boring, eccentric, flight ==================Dictionary ================= Enter ‘I’ to Insert a definition in the dictionary Enter ‘L’ to Lookup a definition in the dictionary Enter ‘A’ to print All the words in the dictionary Enter ‘C’ to print the Count of all words in the dictionary Enter ‘Q’ to quit the program =========================================== Please enter your command: c
4 ==================Dictionary ================= Enter ‘I’ to Insert a definition in the dictionary Enter ‘L’ to Lookup a definition in the dictionary Enter ‘A’ to print All the words in the dictionary Enter ‘C’ to print the Count of all words in the dictionary Enter ‘Q’ to quit the program =========================================== Please enter your command: q
work through zybooks. The most recent of your highest scoring submissions prior to the deadline of 17:00 on Thursday, November 0th will be used as part of your score for this assignment. Additional grading tests will then be run against your highest scoring submission to determine the rest of your assignment grade.