Assignment 1- C++ Visual Studio 2019
This assignment requires you to solve three programming problems, and to implement your solution in C++. You will be assessed by your final delivery. This is an individual assignment. No collaboration is permitted.
Problems:
1) Change the linked list implementation of class List2 available in folder N:Assignment1LinkedList in the following two ways: Save problems as Problem1a.cpp, Problem1b.cpp
a) Convert it to a circular list. The node after the last node should be the first node. The node before the first node should be the last node. Do not change file list2.h. Do not change the implementation of class Node.
i) Implement all operations currently available in the class List.
ii) Add a method empty(), which should return true if the circular list is empty and false otherwise.
iii) Add a method print() to print the values in the nodes of the circular list, from the first to the last node.
b) Use your circular list implementation to implement a circular queue in the following three ways:
• Using composition
• Overriding selected public methods with private methods
• Using private inheritance.
The circular queue should expose only the following methods:
back Returns the value of the last (most recently added) element at the back of the queue.
empty Tests if the queue is empty.
front Returns the value of the element at the front of the queue.
pop Removes an element from the front of the queue
push Adds an element to the back of the queue.
size Returns the number of elements in the queue.
print Prints all values in the queue, from the front to the back.
[40 points]
2) Implement a program to evaluate infix arithmetic expressions containing integer operands and the operators + (addition), – (subtraction), * (multiplication), / (division) and pairs of parentheses, properly nested. Use the following two-stack algorithm (by E. W. Dijkstra):
• If the next token in the expression is an integer, push the integer onto the value stack.
• If the next token in the expression is an operator,
o If the operator stack is empty or the priority of the operator is greater than the priority of the operator at the top of the operator stack, push the operator onto the operator stack.
o Otherwise pop an operator and two integers; push the result of applying that operator to those integers onto the value stack. Then decide again what to do with the operator at the next token.
• If the token in the expression is a left parenthesis, push it onto the operator stack.
• If the next token in the expression is a right parenthesis: pop an operator and two integers; push the result of applying that operator to those integers onto the value stack. Continue until the top of the operator stack is a left parenthesis. Then pop the left parenthesis and ignore the right parenthesis.
• At the end of the expression, operators are popped off and evaluated (popping the operands and pushing the results) until the operator stack is empty
o At this point, the operand stack should have exactly one number in it – the result of the evaluation of the expression.
Provide a user-friendly way to enter expressions to be evaluated.
Save problems as Problem2.cpp
[30 points]
3) Consider the binary search tree implementation in file N:Assignment1BinSearchTreebintree.cp
Save problems as Problem3.cpp
a) Add to the TreeNode class a pointer to the parent node. Modify the insert and erase functions to properly set those pointers.
b) Then define a TreeIterator class that contains a pointer to a TreeNode and has member functions get and next.
i) The iterator’s get member function should return the data value of the node to which it points.
ii) The iterator’s next member function should find the next element in in-order traversal.
• If the current node has a right child, then the next node is the leftmost leave of the right child.
• If the current node does not have a right child, keep moving up to the parent until the previously traversed node is a left child. The next node is the parent of this left child.
c) Add a begin member function to the BinarySearchTree class. It should return an iterator that points to the leftmost leaf of the tree.
[30 points]
Development Requirements
- Constraints. Coding must use C++ and generate an executable file.
- Dependencies. You are encouraged to use global constants, but your program must not declare any global variables, whether of primitive data types, user-defined data types, arrays, file streams, or other. No goto statements are allowed.
- Standards. Your programs must meet the programming standards for this course (attached below).
Delivery
All your source code files (.cpp and .h) and any data files (if applicable) must be placed in the directory Assignment1 in your personal folder. Make separate subfolders Problem1a, Problem1b, Problem2 and Problem3. You should name the source files containing your main programs Problem1a.cpp, Problem1b.cpp, Problem2.cpp and Problem3.cpp.
NOTE: Please do not submit whole Visual Studio projects or solutions!!
Also submit in subfolder Documentation of your submission folder:
A. Grading sheet (supplied at the end of this file) with sections 1, 2 and 3 completed to show what you have done.
B. For each problem:
• A class diagram of the solution
• Optionally, structure diagrams or pseudocode showing the design of the algorithms
• A test plan showing:
(a) Check-points, with a clearly indicated result (Y or N)
(b) Test data and results in a table with three columns:
• test input (printed)
• expected results (printed)
• the actual results of your testing written in by hand
(c) A brief analysis of any known errors, which the program still produces. If there are no known errors, write a statement to this effect.
• Optionally, sample copies of any printed reports produced by your program (if applicable).