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

Sale!