CIS 223
Assignment Number 7S-97
A Simple Expression Evaluation Problem

Reading: Carrano Chapters 2 and 5. See also, examples in Anthology, Section 9.

Programming: Individual Project -- not to be done in groups.

This assignment involves the use of classes, class templates, recursion, and the use of objects in constructing a higher level solution to a programming problem. You are responsible for the implementation of only a portion of the assignment (as described below).

Write a program (The Expression Evaluator) to read in an expression involving integer constants, parentheses, and the six operators +, -, *, /, %, and @ (for exponentiation) and compute the value of the expres- sion. If you have questions or problems, make an appointment to see me or the Lab Assistant. ALSO -- bring questions to class or lab. If you have them, others probably do too.

Turn In: YOU ARE EXPECTED TO CODE THE add_term AND mul_term FUNCTIONS OF THE EXPRESSION EVALUATOR. You will also need to convert the stack class to a class template (with the parameter T used to represent the type of the base elements of the stack) and then use that template as the basis for defining the stack class of integers that you need to solve this problem. EVERYTHING ELSE IS GIVEN. BUT YOU ARE RESPONSIBLE FOR COMPLETE- LY UNDERSTANDING ALL CODE HANDED OUT. SOME EXPLANATIONS OF THIS CODE CAN BE FOUND IN THIS DOCUMENT AND SOME EXPLANATIONS WILL BE GIVEN IN CLASS.

You should turn in your final working program and the output from no more than a half-dozen carefully selected test cases. We will later test your program on an input string given by the lab assistant in the lab. The only thing I will promise you is that once all illegal characters are eliminated, you will have left a string that represents a legal integer computation in C. -- i.e.,

     
                   67*((5-7*8)@342%(10-1)

The only errors you need to check for are illegal characters in the string; you may assume that the string is otherwise syntactically correct. All output should be nicely labeled and clearly understandable.

Finally: The syntax diagrams used in the design of the expression evaluator are attached. Except for the code for which you are responsible, the rest of the code for this project may be found on the web site for CIS 223.

Due Date: To be determined.

NOTES ~~~
GENERAL DESIGN ISSUES:

There are four major components in the programming system for solving this problem:

the main program;
the lexical analyzer class, which is responsible for returning to the main program the next token (integers, operators, parentheses from the input stream as needed;
a stack class template (for pushing and popping operands);
the expression evaluator algorithm.

If these components are implemented correctly, the evaluator component will be able to call member functions of the stack class when it needs to push or pop expression operands on or off the stack. The evaluator should be able to call the get_token member function of the lexical analyzer class whenever it needs to know what the next token is in the string of characters. ALL OF THE PROCESSING RELATED TO THE INPUT STRING AND THE STACK SHOULD BE COMPLETELY HIDDEN FROM THE EVALUATOR.

*** A FEW NOTES ABOUT THE EVALUATOR:

The structure of the evaluator function is based upon the structure of the syntax diagrams for "expression" as handed out in class. We will be discussing the general non-recursive and recursive algorithms for expression evaluation in class, and spend at least some time on the details of this function.

*** A FEW NOTES ABOUT THE INPUT EXPRESSION:

Using the appropriate iostream function you can read the string repre- sentation of the expression to be processed from an external file. You may assume that any character may appear in the string including blanks, but the only legal characters are:

decimal digits characters '0', '1', ... '9';
the integer arithmetic operators '+', '-', '*', '/', '%' and '@' are legal (% is the mod operator and @ (which is the power operator);
parenthesis () are legal;
blanks are legal.

All other characters and even the blank are to be eliminated before you begin processing (either during reading, or after reading the string).

*** HOW TO TELL IF A CHARACTER BELONGS TO SOME SET OF CHARACTERS (e.g., some set of legal characters):

To tell if a character is in the "set" of legal characters, either use the set class that we have put up on the web, OR ... you might define a string

              char legal_characters [] = "0123456789+-*/%@()"

and then use one of the standard C string.h functions to test whether or not a particular character ch is a member of this string. NOTE: This declaration may not be adequately implemented on all compilers.

*** PROCESSING THE INPUT STREAM:

A function named get_token has been included in the lexical analyzer class. Each time get_token is called, it should scan the input character string and return a symbolic representation of the next token in the string. For example, using enumerators, you might return lpar for a left parenthesis, plus for +, minus for -, mod for %, and number for an integer. I am assuming here, for example, that we have defined something like

              enum symbol {lpar, rpar, plus, minus, mod, div, mult, power, number};

In the case of a number, you will need to compute the value and return it as well. Again, perhaps another library function can help you with this conversion. NOTE THAT EXCEPT FOR NUMBERS, THE ORIGINAL TOKENS THEMSELVES ARE NEVER RETURNED. THE EXPRESSION EVALUATOR HAS NO NEED TO KNOW ANYTHING ABOUT THEM.

Simple Expression Syntax Diagrams

Return to Previous Page

CIS 223 Assignment Number 7S-97 A Simple Expression Evaluation Problem