Write in C++

Introduction: Your task for this assignment is to write a program that is able to decode IDs from two different bars (Bar1 and Bar2), check for duplicate IDs, sort the IDs in ascending order, and print a report of the IDs indicating which IDs are guilty and which are innocent. An ID is guilty if it appears more than once, and an ID is innocent if it appears only once. Assumptions: Each input file may contain a maximum of 100 IDs Bar names will always be Bar1 and Bar2 Each ID may vary in length (i.e. 12345, 9019, 23, etc.) Each encoded ID contains only numbers and parentheses Each encoded ID has n characters, where 1 <= n <= 30 Each decoded ID has m characters, where 1 <= m <= 10 Encoded IDs will always have balanced parenthesis There will be may be empty lines in the input file An ID is considered guilty if it appears more than once (regardless of what bar it comes from).

Rules for Decoding and Output: For decoding the IDs, reverse the numbers in each pair of matching parentheses, starting from the innermost pair. Below are the steps to decode the ID (4(23)1):

Step 1: You start with (4(23)1) as your encoded ID. Begin decoding from the innermost parentheses and reverse the numbers, so you reverse the numbers 2 and the 3. Now your encoded ID is (4321)

Step 2: Your encoded ID is now (4321), so reverse the number 4, 3, 2, and 1 since they are inside parentheses. After reversing the numbers you are left with 1234. There are no parenthesis left so there is nothing left to decode. Your decoded ID is 1234.

For the output, you should print both guilty and innocent IDs. You should print guilty IDs first and then the innocent IDs. IDs should be printed in ascending order for both guilty and innocent. The format for the output is shown below.

You must use a linked list to implement your solution and your linked list operations should only use recursion. Your linked list class should not contain any for or while loops. You may use for and/or while loops in your main function but not in your linked list class.

Example input and output:

input1.txt

Bar1 10(01) (4(23)1) Bar2 (20)02 Bar1 (20)21 Bar2 3(021) (4321)

output1.txt

Guilty: 1234 Innocent: 0202 0221 1010 3120