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.

Roman numerals are as follows: 1 = I

5 = V

10 = X

50 = L

100 = C

500 = D

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

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 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.