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.

• 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

• 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!