The will only use the operators of addition, subtraction, multiplication, division and the parentheses. It will also only contain unsigned (i.e. positive) integer values. We obviously could allow for more operators and more types of values, but the purpose of this assignment is to focus on writing C++ classes and not on complicated arithmetic expressions.

Infix Expression are when the operators of addition, subtraction, multiplication and division are listed IN between the values. Infix Expressions require the use of parentheses to express non- standard precedence. Examples of Infix Expressions are:

42 + 64 60 + 43 * 18 + 57 (60 + 43) * (18 + 57) 18 12 3 18 (12 3)

The simplest algorithm to evaluate an Infix Expression includes a translation from an Infix expression to a Postfix Expression and then evaluating the Postfix Expression. The algorithm that we will use combines the translation and evaluation into a single algorithm. So the following short discussion of Postfix expression may be useful in understanding our algorithm. Note that all of these algorithms requires the use of stacks; hence, the reason for the stack class.

Postfix Expressions are when the operators of addition, subtraction, multiplication and division are list AFTER (i.e. post) the values. Postfix Expression never require the use of parentheses to express non-standard precedence. The fact that postfix expressions do not need parentheses makes them much easier to evaluate than infix expressions. In fact, most computers first convert infix expression to a postfix expression and then evaluate that postfix expression.

Command	Description
q	Quit the program.
?	List the commands used by this program and a brief description of how to use each one.
	Evaluate the given infix expression and display its result.

A postfix expression is evaluated using a stack. When a value is encountered, it is pushed onto the stack. When an operator is encountered, two values are popped from the stack. Those values are evaluated using the operation implied by the operator. Then the result is pushed back onto the stack. When the end of a postfix expression is encountered, the value on the top of the stack is the result of the expression. There should only be one value on the stack when the end of the postfix expression is encountered.

Examples of Postfix Expressions are:

42 64 + 60 43 18 * + 57 + 60 43 + 18 57 + * 18 12 3 18 12 3

Both the algorithm to convert an infix expression to a postfix expression and the algorithm to evaluate a postfix expression require the use of stacks. Note that the conversion algorithm requires a stack of operators, while the evaluation algorithm requires a stack of values.

For this program, you are to write the following methods for the dynamic array stack class:

void init( ); bool isEmpty ( ); void push (data); data top ( ); void pop ( ); void reset ( );

// initialize the stack for use THIS MAY BE A CONSTRUCTOR // return true if the stack has no members // add the data to the top of stack; grow dynamic array if needed // return the data value on the top of the stack

// remove the data value from the top of the stack // clear the stack to remove any values it contains

For this program, your dynamic array MUST start with 2 positions in the array. When the array needs to grow, it size MUST grow by 2 additional positions each time (note the array to grow in size from 2 to 4 to 6 to 8 to 10 to ...). Note the init( ) method to set up the stack should really be a constructor (but could be a normal method). You can also write a topPop( ) method that combine both the top and pop operations in a single method. Also, note that since the values from the infix expressions will all be integer values (we will only do integer division), and since the operators can all be represented as characters (which is a sub-class of integers), you are more than welcome to write a single stack class which store integers to be used for both stacks.

The instance/variable containing for each stack MUST be declared as a local variable to some method (it may be as a local variable to a method other than main( ) ). It may NOT be global.Each operation performed on the stack MUST be done in its own method. ALL data members of the stack class MUST use access modifier of private.

Algorithm for Infix to Postfix Conversation and Postfix Evaluation

When getting the input for an infix expression, the program proj5Base.cpp breaks everything down into tokens. There are 3 types of tokens we are mostly concerned with: an OPERATOR token, a VALUE token and the EndOfLine token. The code in the function processExpression() already checks for these token but you will need to add the code how to interact with the stacks.

First step: Empty both the OperatorStack and the ValueStack

Second Step: While (the current token is not the EndOfLine Token)

if ( the current token is a VALUE ) push the value onto the ValueStack

if ( the current token is an OPERATOR ) if ( the current operator is an Open Parenthesis )

push the Open Parenthesis onto the OperatorStack if ( the current operator is + or - )

while ( the OperatorStack is not Empty && the top of the OperatorStack is +, -, * or / )

popAndEval ( ) push the current operator on the OperatorStack

if ( the current operator is * or / ) while ( the OperatorStack is not Empty &&

the top of the OperatorStack is * or / ) popAndEval ( )

push the current operator on the OperatorStack if ( the current operator is a Closing Parenthesis )

while ( the Operator Stack is not Empty && the top of the OperatorStack is not an Open Parenthesis )

popAndEval ( ) if (the OperatorStack is Empty )

print an error message

else get the next token from the input

pop the Open Parenthesis from the OperatorStack

Third Step: Once the EndOfLine token is encountered

while (the OperatorStack is not Empty ) popAndEval ( )

Print out the top of the ValueStack at the result of the expression Popping the ValueStack should make it empty, print error if not empty

The error statements in the above algorithm should only occur if an invalid infix expression is given as input. You are not required to check for any other errors in the input.

The above algorithm calls another algorithm called popAndEval ( ) which is shown below. This algorithm plays a critical role in the overall Evaluation of our expressions.

op = top (OperatorStack) pop (OperatorStack) v2 = top (ValueStack) pop (ValueStack)

v1 = top (ValueStack) pop (ValueStack) v3 = eval ( v1, op, v2 ) push (ValueStack, v3)

To keep some of the error handling/recovery simple for this project, if you are trying to perform a top operation on an empty ValueStack, print out an error message and return the value of -999. If the operator op for eval ( ) is not one of *, /, + or -, print out and error message and return the value of -999.

Base code is here:

https://www.cs.uic.edu/pub/CS211/ProjectF18/proj5Base.cpp