$40.99
CSCE221- Assignment 3: Part 1 and 2 Solved
Problem 1
Listing 1 shows the Copy Constructor for the TemplateDoublyLinkedList.h
Listing 1: Copy Constructor for Doubly Linked List from TemplateDoublyLinkedList.h
// copy constructor template <typename T>
DoublyLinkedList<T>::DoublyLinkedList(const DoublyLinkedList<T>& dll) {
// Initialize the list
header.next = &trailer; //Make an empty list trailer.prev = &header;
DListNode<T>* temp = dll.getFirst(); while(temp != dll.getAfterLast()){ this->insertLast(temp->getElem()); temp = temp->getNext();
}
}
5
10
1) As show, if we compute the big-O of the function, we find the while loop makes our code run through every element in the Doubly Linked List. This leads us to conclude
O(n) (1)
A linear complexity.
Listing 2 shows the Assignment Constructor for the DoublyLinkedList.
Listing 2: Assignemnt Operator for Doubly Linked List from TemplateDoublyLinkedList.h
// assignment operator template <typename T>
DoublyLinkedList<T>& DoublyLinkedList<T>::operator=(const DoublyLinkedList<T>& dll)
{
if(!isEmpty()){ //Cheack if list is not empty while(header.next != &trailer){ removeFirst();
}
}
DListNode<T>* temp = dll.getFirst(); //Create a temporary node while(temp != dll.getAfterLast()){
this->insertLast(temp->getElem()); //Copy each node over temp = temp->getNext();
} return *this; //Return pointer to new assigned list
}
5
10
15
2) We first check whether our doubly linked list is empty. If it is not, we proceed to remove each element of the first list so that we can then assign the elements of the second list to the first. The second while loop will run through each node of the second list and create new nodes for the first list.
Wee see the time complexity to be:
O(n) (2)
A linear complexity.
Listing 3: insertFirst() and insertLast() for Doubly Linked List from TemplateDoublyLinkedList.h
// insert the object to the first of the linked list template <typename T>
void DoublyLinkedList<T>::insertFirst(T newobj)
{
DListNode<T> *newNode = new DListNode<T>(newobj, &header, header.next); header.next->prev = newNode; //Insert a new node into the list header.next = newNode;
}
// insert the object to the last of the linked list template <typename T>
void DoublyLinkedList<T>::insertLast(T newobj)
{
DListNode<T> *newNode = new DListNode<T>(newobj, trailer.prev,&trailer); trailer.prev->next = newNode; //Insert at the end of the Doubly Linked List.
trailer.prev = newNode;
}
5
10
15
3) This time complexity is a simple
O(1) (3)
A constant complexity. This is because we do not need to run through the elements to find the last one. The trailer and header pointers gives us the ability to quickly insert nodes before and/or after these pointer.
Listing 4: removeFirst() and removeLast() for Doubly Linked List from TemplateDoublyLinkedList.h
// remove the first object of the list template <typename T>
T DoublyLinkedList<T>::removeFirst()
{ if (isEmpty())
throw EmptyDLinkedListException("Empty Doubly Linked List");
DListNode<T> *node = header.next; //Reference the deleted node node->next->prev = &header; //move to next element; repointer header.next = node->next; //Change header to second node T obj = node->obj; delete node; return obj;
}
// remove the last object of the list template <typename T>
T DoublyLinkedList<T>::removeLast()
{ if (isEmpty())
throw EmptyDLinkedListException("Empty Doubly Linked List"); DListNode<T> *node = trailer.prev; node->prev->next = &trailer; trailer.prev = node->prev;
T obj = node->obj;
5
10
15
20
delete node; return obj;
}
25
4) The time complexity for these two functions will be a simple
O(1) (4)
Because we do not need to iterate through every element of the list to choose the position we want.
Listing 5: Destructor function for Doubly Linked List from TemplateDoublyLinkedList.h
// destructor template <typename T>
DoublyLinkedList<T>::˜DoublyLinkedList<T>()
{
DListNode<T> *prev_node, *node = header.next; //Create two pointers while (node != &trailer) {
prev_node = node; //Assigne prev_node to point at node node = node->next;
delete prev_node; //Go deleting the nodes at pre_node
}
header.next = &trailer; trailer.prev = &header;
}
5
10
5) The destructor must run through every element of the doubly linked list to delete the nodes and elements from the list. The time complexity for the while loop in this function will be linear:
O(n) (5)
Listing 6: first() and last() for Doubly Linked List from TemplateDoublyLinkedList.h
// return the first object template <typename T>
T DoublyLinkedList<T>::first() const
{ if (isEmpty())
throw EmptyDLinkedListException("Empty Doubly Linked List");
return header.next->obj;
}
// return the last object template <typename T>
T DoublyLinkedList<T>::last() const
{ if (isEmpty())
throw EmptyDLinkedListException("Empty Doubly Linked List");
return trailer.prev->obj;
}
5 10
15
6) The header and trailer pointers give us a quick access to the first and last elements in the Doubly Linked List. We do not need to run though the elements in the list. The time complexity of these two functions will be constant:
O(1) (6)
Listing 7: operator¡¡ for Doubly Linked List from TemplateDoublyLinkedList.h
// output operator template <typename T>
ostream& operator<<(ostream& out, const DoublyLinkedList<T>& dll) {
DListNode<T>* temp = dll.getFirst(); //Make temp point to the first element while(temp != dll.getAfterLast()){ //Iterate through the list
out << temp->getElem() << " "; //Output the elements in the nodes temp = temp->getNext();
} return out;
}
5
10
7) We see that the while loop depends on the number of nodes in our Doubly Linked List. Therefor the time complexity will be:
O(n) (7)
Figure 1: Screenshot of the Templated DoublyLinkedList
COMPSCI 221 (Leyk 4:20pm): Programming Assignment 3 #1 Problem 1
Figure 2: Screenshot of the DoublyLinkedList.cpp
Problem 1
In this assignment, we are using the Doubly Linked List ADTs that are implements as a templated Queue and Stack data structure. The Doubly Linked List consists of the header and trailer pointer and nodes that have points to the previous and next element in the list. The node contains the templated element which in this assignment is a double and a string. The algorithms used here are contained within the Parser class and the Evaluator class.
The classes that I choose to implement were the LinkedQueue, LinkedStacked, Evaluator and Parser classes. By building upon the templated LinkedQueue and LinkedStack classes, I created the parser class which is used to convert an infix expression that the user inputs into a postFix expression that the Evaluator class will ultimately evaluate. Along the way, the Evaluator class asks the user for numerical entries if the user included variables for the infix notation. These are all called by the main file which displays the user menu and requests that the user submit the equation via keyboard input.
The reason why I choose these classes was due to the example presented in class and the logic that was behind the associated input priority and stack priority of the operators +,−,∗,/,, (,). The Parser class correctly sorts the input and creates an postFix notation of the input.
Parser
The Parser class contains the following Private members:
LinkedQueue < std :: string > postFixQueue; - A queue that holds the postFix notation
LinkedQueue < std :: string > inFixQueue; - A queue that holds the inFix notation
LinkedQueue < std :: string > tokenize(std::string input); - Takes a string as an input and converts the string into nodes that are pushed onto a LinkedQueue. If the parenthesis are not balanced, then an error is thrown and the program closes. This function returns the inFix notation. This function is
O(n) (1)
linear complexity.
LinkedQueue < std :: string > toPostFix(LinkedQueue < std :: string > in); - Based on the order of precedence on the slides, this function uses the two data structures, Stack and Queue, and correctly sort and create a postFix notation of the input expression. If the user used variables in their expression, the variables are still present in the postFix notation. This function is
O(n) (2)
linear complexity.
And the following Public members:
Parser(std :: strings) {tokenize(s);}; - The Parser constructor which call the function tokenize.
LinkedQueue < std :: string > getPostFix(); - Returns the private variable PostFixQueue. This function is
O(1) (3)
constant complexity.
Problem 1 continued on next page...
Problem 1 (continued)
int inputPriority(string temp); - Assigns a specific value to the input operator from the string. This value is then later used by the parse to correctly place the operator in the postFix expression. This function is
O(n) (4)
linear complexity.
int stackPriority(string temp); - Assigns a specific value to the stack operator from the string. This value is then later used by the parse to correctly place the operator in the postFix expression. This function is
O(n) (5)
linear complexity.
bool isBalanced(); - This function counts the instances of the left prenthesis and right parentheses and returns a bool if the expression is balanced or not. This function is
O(1)
A constant complexity.
• void printInfix(); - Prints the Infix from inFixQueue. This function is
(6)
O(1)
A constant complexity.
• void printPostfix(); - Prints the Postfix from postFixQueue. This function is
(7)
O(1)
(8)
constant complexity.
Evaluator The Evaluator class contains the following Private members:
LinkedQueue < std :: string > postFixQueue; - A queue that holds the postFix notation
LinkedQueue < std :: string > eval; - A queue that holds the inFix notation
double value; - This returns the final answer as a double.
string tres; - Global string for the answer that returns from the double evaluation.
string before double; - String that later gets converted to a double.
And the following Public members.
Evaluator(LinkedQueue < std :: string > par) - This is the default constructor for the Evaluator class. The input is a LinkedQueue object of strings which contains the postFix expression that will be evaluated.
Problem 1 continued on next page...
Problem 1 (continued)
double getValue(); - This function returns the value of the final answer as a double. This function is
O(1) (9)
constant complexity.
string switchCase(double a, double b, string cur num); - This function will evaluate the specific operations that is requested from the postFix notation. The arguments are two strings that will be operated on. This function returns a string that will be pushed onto the stack for later operations. This function is
O(1) (10)
constant complexity.
LinkedQueue < std :: string > get digits(LinkedQueue < std :: string > in); - If the user submitted the expression using variables, this function will request the user to submit numerical entries for the said variables. This function returns a postFix queue that contains numbers and operators. This function is
O(n) (11)
linear complexity.
For correctness, I inputted various expression that contained illegal characters. The program caught these characters correctly and threw an error message which then ended the program. These characters were caught because I created a test with the use of ASCII characters and their acceptable ranges.
Below I have demonstrated a few test cases that use illegal characters and are caught by the program. As shown, two instances of unbalanced parenthesis and illegal expressions are caught from the input, thus proving the correctness of the program!
Figure 1: Illegal characters test.
Figure 2: A run of the postFix Evaluator program.
Figure 3: Another screenshot of the program
