Reference no: EM132333617

Assignment -

Key Concepts - In this assignment, you will gain experience implementing and using a linked list and stack data structure. It should also give you a better understanding of dynamic allocation, templates, and recursion.

Problem Description - The following is a modified version of a problem taken from the text, C++ How to Program by Dietel and Dietel.

Stacks are used by compilers to help in the process of evaluating expressions and generating machine language code. We will investigate how compilers evaluate arithmetic expressions consisting only of constants, operators, and parentheses.

Humans generally write expressions like 3 + 4 and 7 / 9 in which the operator (+ or / here) is written between its operands - this is called infix notation. Computers "prefer" postfix notation in which the operator is written to the right of its two operands. The preceding infix expressions would appear in postfix notation as 3 4 + and 7 9 /, respectively.

To evaluate a complex infix expression, a compiler would first convert the expression to postfix notation, and then evaluate the postfix version of the expression. Each of these algorithms requires only a single left-to-right pass of the expression. Each algorithm uses a stack object in support of its operation.

You will write a C++ version of the infix-to-postfix conversion algorithm. You will discover that code you write to do this exercise can help you implement a complete working compiler.

The program you will write should convert an ordinary infix arithmetic expression read from a text file (assume a valid expression is entered) with single digit integers such as (6 + 2) * 5 - 8 / 4 to a postfix expression. The postfix version of the preceding infix expression is 6 2 + 5 * 8 4 / -

The program will then further evaluate the postfix expression into an integer.

In order for this problem to be solved, we will need to utilize a stack that should be maintained with stack nodes that each contain a data member and a pointer to the next stack node. Furthermore, you will implement a template class for linked lists. Essentially, you must use the code provided to you in the course slides and add new functions to the existing List class as described below. Therefore, your List must be a class template that is implemented using pointers. If you use another approach other than what I have stated, you will receive a failing grade even if your code manages to implement the required functionality.

A sample test file, testlist[1].cpp is provided. A sample output file, program1_output.txt is also provided. You can use this sample test file to make sure you define your functions properly. However, you should add other tests to ensure that your program is working correctly.

You can create your own test file for the Stack classes that you will build.

Requirements - In order to not get overwhelmed, please do the work in the order listed in this document.

Part 1 - Enhance the List template class discussed in the course by adding the functions listed below. Note that in no instance must any of the functions swap the data contents of the nodes - the node pointers themselves must be changed when swapping elements. Please use the exact names that have been listed below in order for my test program to work. Use the testfile to determine the return type and parameter list for each function based on it is used.

• Write a function, called add_n(int n, ListNode<NODETYPE> &value), that adds an element after the nth element of a list.
• Write a function, called concat(List<NODETYPE> &list2), that concatenates two linked lists. (Connects the two linked lists so the second follows the first.) Once this function is executed, list2 should end up being empty because the calling List object should take its nodes as part of its own list.
• Write a function, called reverse(), that reverses a list, so the last node becomes the first, etc.
• Write a function, called remove_n(int n), that removes the nth element of a list.
• Write a function, called sort(), that sorts a list in increasing order.
• Write a function, called merge(List<NODETYPE> &list2), that merges one sorted list into another sorted list to create a single list.
• Write a function, called add_in(ListNode<NODETYPE> &value), that inserts an element in the correct position in a sorted linked list. This assumes the list IS SORTED already.
• Write a function, called remove(ListNode<NODETYPE> &value), that removes an element with the given value.
• Write a function, called count(), that returns the number of elements in the list.
• Overload the assignment operator= and the output operator<< to allow one List to be assigned to another List and to print a List using cout respectively.

Part 2 - You have been provided with Stack.h, StackNode.h and Stack2.h. You must complete all missing code from those classes in order to use class Stack2 which inherits from Stack. Again, feel free to use your own driver program to test that your stack classes work properly before moving on to the next step.

Part 3 - Once you have completed this step, then you must implement all the missing functions in class MathExpression which has also been provided to you and which uses both Stack.h and Stack2.

A MathExpression object is comprised of three data members, a char array representing an infix expression, a char array representing the same infix expression but in postfix notation, and finally an int that represents the postfix expression after it has been evaluated.

The functions that require further explanation are described in attached file.

Part 4 - After you have completed the MathExpression class, you must test it using the driver program provided to you. The driver program is very simple and only attempts to test some of the more vital functions of the class. At this point, you should have used the driver program for the List, Stack and MathExpression classes in order to test each of those classes independently.

Part 5 - You must now combine all of these classes into one project and create a driver program to achieve the intended goal of the assignment. The driver program must do the following:

Create a List of type MathExpression. You will then open a file called infixData.dat and read its data. The file is comprised of an arbitrary number of infix expressions, one per line. You must read each line using the List's overloaded fstream operator>>. As you read each line of the file, you must create a MathExpression object by passing the infix expression read into its constructor. The constructor for MathExpression should automatically call the functions that will then initialize its other two data members, postfixExpression_ and value_ respectively using the functions it has. When you are done, you should have a List of MathExpression objects, each composed of an infix expression, a postfix expression that is based upon the infix expression and finally, an int which is the evaluated value of the postfix expression. You are to then print these values to the screen using the overloaded output operator <<.

Attachment:- External Files & Classes Assignment Files.rar