IUP Computer Science
CO 310 Fall 1996

Project 4
(Due   5 November 1996)

You are given a template definition for a Stack class. It is in the file EXPSTACK.H in o:\JLW\310 or L:JLW\310 or from 310LIB:. Using it, you are to write a program that can directly evaluate any infix expression that uses long int numbers, operators +, -, *, /, and ^, and parentheses for grouping subexpressions.

The operators have the usual precedence and order of evaluation: exponentiation (^) has highest priority and is performed right to left; multiplication (*) and division (/) have next highest and are evaluated left to right; addition (+) and subtraction (-) have lowest priority and are evaluated left to right. Parenthesized subexpressions are evaluated as soon as they are complete. So, in the following example, one correct evaluation 

29 - 7 + 6 * (9 + 8 - 13) ^ 3 ^ 2 / (256 - 3 * 5)
order would be: First, subtract 7 from 29 (giving 22); add 9 and 8 (giving 17); then, subtract 13 (giving 4); raise 3 to the power of 2 (giving 9); then raise 4 to the power of 9 (giving 262144); multiply 6 by 262144 (giving 1572864); multiply 3 by 5 (giving 15) and subtract it from 256 (giving 241); then divide 1572864 by 241 (giving 6526); and finally add 22 and 6526 (giving 6548 as the final answer).

To implement this evaluation, you will probably need three stacks: one for operators, one for priorities, and one for operands. You will need to assign the operators appropriate priorities; you may also want to assign the left parenthesis a priority. Your algorithm should them act approximately as follows:

Read the expression, component by component
For each expression component:
- If it is an operand (number), stack it.
- If it is an operator, check the previous operator and either stack the new operator or evaluate the previous operator (top of stack) and then stack the new one, depending on how the new operator's priority compares to the previous operator's priority. (The evaluation may occur several times before stacking the new operator.)
- If it is a left parenthesis, stack it.
- If it is a right parenthesis, evaluate back to a left parenthesis.
- If it is the end of the line, evaluate any remaining operators on the stack. The value of the whole expression should then be the only thing left on the operand stack.

Below is an illustration of the changes for the operator and operand stacks in evaluating the expression above. The stacks are shown side by side at each point an evaluation is needed (there wasn't room for the last two evaluations). The priority stack is not shown. 

                   2                          5
       8 +  13 -   3 ^   9                    3 *       15
       9 (  17 (   4 ^   4 ^  262144        256 -      256 -      241
7      6 *   6 *   6 *   6 *       6 *  1572864 (  1572864 (  1572864 /
29 -  22 +  22 +  22 +  22 +      22 +       22 +       22 +       22 +
To evaluate an operator, take two operands off the operand stack, one operator off the operator stack, perform the operation and put the result back on the operand stack.

In addition to being able to evaluate any valid expression that fits on a single line, your program must detect and respond to errors in the expression. Whenever the expression is invalid, your program must display an appropriate error message. That is, the program should not just say "Error"; it should indicate what the error is. Here some examples that should result in error messages. 

83 + 15 + 44 +				Missing operand/Extra operator
6 * / 12				Missing operand/Extra operator
15 - 4 / (23 - 15 - 8) + 55		Divide by zero
67 * (25 - 6) + 5)			Missing left parenthesis
+23 * 4					Missing operand/Extra operator
32 * (3 + 52 / 2			Missing right parenthesis
If any character other than a number, a valid operator, or a parenthesis appears in an expression, your program should terminate. The program should repeatedly read in expressions and either display the value of the whole expression or report an error until an illegal character is read in. For example, any letter would be illegal.

Notes: When an expression is entered, any number of spaces (including none) are allowed between each two expression components. Also, you are NOT allowed to convert the infix expression that is input to a postfix expression before evaluating it.

Hand in a printout of your program and a copy of your main program on a diskette.

Stack Template Member Function Prototypes (assuming the Stack is declared as Stack) 

void Push (const Etype &)	Push an item of type Etype
void Pop (void)			Pop the top item from the Stack
const Etype & Top (void)	Return the value of the top item
int IsEmpty (void)		Determine if the Stack is empty
int IsFull (void)		Determine if the Stack is full
void MakeEmpty (void)		Remove all items from the Stack