Assignment Instructions:

For this assignment you will be writing a program that is capable of parsing and calculating the result for a simple mathematical expression which includes parenthesis, integer numbers, and addition, subtraction, multiplication, and $($integer $/$ true$)$ division operators. In order to accomplish this you will need to implement functions based on algorithms described below in addition to Python classes representing the stack and queue data structures.

Stack Class:

Implement a stack data structure which contains methods for adding a value to the stack $($push$),$ removing a value from the stack $($pop$),$ looking at the top value on the stack $($top$),$ and whether the stack contains any elements $($is$\_$empty$).$

If you would like, you may use the code for the Stack class in the textbook in chapter $6\mathrm{.}1.$

Queue Class:

Implement a queue data structure which contains methods for adding a value to the queue $($enqueuer$),$ removing a value from the queue $($dequeue$),$ looking at the value at the front of the queue $($first$),$ and determining whether the queue contains any elements $($is$\_$empty$).$

If you would like, you may use the code for the Queue class in the textbook in chapter $6\mathrm{.}2.$

Calculator module:

Create a Calculator.py module that will contain the following functions that you will need in order to evaluate a simple mathematical expression.

expression$\_$to$\_$queue function:

This function should take a single argument of type String and convert it into a queue. This can be done by breaking the String down into the individual operators and operands and inserting them into a queue based on their order within the expression String.

queue$\_$to$\_$expression function:

This function should take a single argument representing a Queue which contains a mathematical expression and convert it into a single String. This can be done by removing elements from the queue and concatenating them onto a String that will be returned once the queue is empty.

postfix$\_$to$\_$infix function:

This function should take a single argument representing a Queue that contains a mathematical expression in postfix notation and produce a different Queue which contains that same mathematical expression represented in infix notation. You may wish to create a dictionary that contains the precedence levels for the different operators. Additional and subtraction have the same precedence as each other, which is lower than than division and multiplication, which also have the same precedence as each other. The following pseudocode algorithm describes how to perform this conversion:

while the input queue is not empty:

remove the first element from the queue.

if the element is a number, then push it to the output queue.

else if the element is a left parenthesis $($i$.$e$."("),$ then:

push it onto the operator stack.

else if the element is a right parenthesis $($i$.$e$.")"),$ then:

while the operator at the top of the operator stack is not a left parenthesis:

pop operators from the operator stack and add them to the output queue.

pop the left bracket from the top of the operator stack.

if the stack runs out without finding a $\text{'}(\text{'},$ then there are mismatched parentheses.

else if the element is an operator $($i$.$e$."+","-","*",$ or $"/")$ then:

while there is an operator at the top of the operator stack and either of the following:

$1)$ the operator at the top of the stack has greater precedence than the element:

$2)$ the operators at the top of the stack is not a left parenthesis

pop operators from the operator stack and add them to the output queue

push the read operator onto the operator stack.

else the element is not valid part of a mathematical expression

if there are no more elements to remove from the input queue:

while there are still elements on the operator stack:

if the element on the top of the stack is a $\text{'}(\text{'},$ there are mismatched parentheses.

pop off the element from the operator stack and add it to the output queue.

return the output queue

evaluate$\_$infix function:

This function should take a single argument representing a Queue that contains a mathematical expression in infix notation and should return the result of evaluating that expression. The following pseudocode algorithm describes how to perform this calculation:

while the input queue is not empty:

remove the first element from the input queue

if the element is an operand $($i$.$e$.,$ it is a number$)$:

push the value to the operands stack

else if the element is an operator $($i$.$e$."+","-","*",$ or $"/")$ then:

pop the right$-$hand operand off of the operands stack

pop the left$-$hand operand off the operands stack

calculate the result of the operation using the two operands and the operator

push the result to the operands stack

if the operands stack has more than one element, the expression is invalid

pop the single value on the operands stack and return the result of the calculation

Testing your program:

I