In C++

Objectives: Implement a linked list Use structures to create nodes for a linked list Use pointers to manipulate a linked list Problem: Doc Brown has configured the DeLorean to go back to the days of the Roman Empire. Unfortunately, the Roman Empire does not use Arabic numerals which is going to make it difficult for Doc to do the proper calculations he needs to get back home. Before he heads back in time, he wants you to create a Roman numeral converter for him.

Pseudocode Details: The sorting method of the linked list o What parameters are expected o Describe logically how you will make the sort universal to sort on Roman or Arabic numeral o Describe the logic for the sorting algorithm you plan to implement Remember that you can treat the linked list like an array logically Input validation o What parameters are expected o How will you validate the file data Searching the linked list o What parameters are expected o How ill you determine if the user entered a Roman numeral or an Arabic numeral o How will you locate the item in the list

Details: Roman numerals are as follows: o 1 = I o 5 = V o 10 = X o 50 = L o 100 = C o 500 = D o 1000 = M Determine if the input given is Roman numeral or Arabic. Convert from given type to the missing type. All numbers will be in the range of 1 4999. Store the file contents in a linked list. o Add the node to the beginning of the list All manipulation of the data will happen in the linked list. o Convert each piece of data to its unlisted counterpart Write the contents of the linked list back to the file at the end of the program. The file may contain invalid data. o If invalid data is identified, ignore the entry in the file. Invalid data: o Arabic numeral outside the given rage. o Invalid characters in Roman numeral. o Invalid characters in Arabic numeral. User will be able to search and sort the data. Use a linear search o Search can be for Arabic or Roman numeral o Do not ask user what type of numeral to search for (-5 points if user is asked) User can type in Arabic or Roman numeral You have to figure out what they typed Implement sorting algorithm of your choice o Sorting algorithm will move nodes (-10 points) o Do not exchange node data o All sorts will sort in ascending order Arabic: smallest to largest number Roman: alphabetical Comment your code generously. Refer to the grading rubric for more details. Use as few variables as possible. Dont waste memory holding a calculation just so you can print it out one time.

User Interface and Input: Create a simple menu interface allowing the user to search and sort the data. The menu will consist of 3 options: 1. Search 2. Sort 3. Exit If the user selects the sort option, provide a sub menu: 1. Sort by Roman numeral 2. Sort by Arabic numeral All user input will be valid. Remember that the file input may not be valid.

File Structure: The file will contain an unknown quantity of numbers to convert. Each number will be on a separate line. The number will be either Arabic or Roman Each line of the file will have the same format o Roman numeral field 16 characters Fixes the 4888 issue Arabic numeral field 4 characters The last line may or may not have a new line at the end Only one of the fields will hold a value on each line o If a field does not hold a value, it will contain all spaces. o If the Roman numeral field contains a space as the first character, you know that the line contains an Arabic numeral

Output: If the user enters the option to search, state whether the item was found or not found ( ) in the console window. If the user enters the option to sort, display the sorted values to the console window. Only display the values for the type of data sorted. For example, if Roman numerals are sorted, only display the Roman numerals in alphabetic order. At the end of the program, write the linked list back to the file used for input.

EXTRA CREDIT OPPORTUNITY 1: Implement a merge sort (20 points) Use the same sorting requirements as above You will need to identify the type of data being sorted before performing the sort You must use the sort if implemented Add a comment at the top of your program o //INSERTION SORT LINES ### - ###, CALL LINE ### o Fill in ### with line numbers

EXTRA CREDIT OPPORTUNITY 2: Validate all input (10 points) This is in addition to the validation mentioned above Validate all user input o Expect the user will type in anything Validate Roman numerals in file o Roman numerals may contain valid characters in wrong order o Examples: IIIX VXI MMLDCCIV Handling invalid input o Invalid user input loop until valid input o Invalid file input ignore line Add a comment at the top of your program o //INPUT VALIDATION