Assignment 3 #2 Doubly Linked List ADTs

Programming Assignment 3 #2
Problem 1
Abstract
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.
1) 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.
2) 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)
A 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)
A linear complexity.
And the following Public members:
• P arser(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)
A constant complexity.
Problem 1 continued on next page. . . Page 2 of 7
Robert Quan COMPSCI 221 (Leyk ): Programming Assignment 3 #2 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)
A 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)
A 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) (6)
A constant complexity.
• void printInfix(); - Prints the Infix from inFixQueue. This function is
O(1) (7)
A constant complexity.
• void printPostfix(); - Prints the Postfix from postFixQueue. This function is
O(1) (8)
A 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. . . Page 3 of 7
Robert Quan COMPSCI 221 (Leyk ): Programming Assignment 3 #2 Problem 1 (continued)
• double getValue(); - This function returns the value of the final answer as a double. This function is
O(1) (9)
A 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)
A 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)
A linear complexity.
3) 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.
4) 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!
Page 4 of 7
Robert Quan COMPSCI 221 (Leyk ): Programming Assignment 3 #2 Problem 1
Figure 1: Illegal characters test.
Page 5 of 7
Robert Quan COMPSCI 221 (Leyk ): Programming Assignment 3 #2 Problem 1
Figure 2: A run of the postFix Evaluator program.
Page 6 of 7
Robert Quan COMPSCI 221 (Leyk ): Programming Assignment 3 #2 Problem 1
Figure 3: Another screenshot of the program
Page 7 of 7