Introduction to Programming (22C:16, 22C:106)

Project 1: Tuesday, 2/25/96

Introduction:

This is the first in a series of 4 programming projects that you are required to complete for this class. Each programming project (except the first) builds on previous projects. At the end of the 4 projects, you would have constructed an assignment evaluator, a program that can understand and evaluate simple assignment statements. The main purpose of these projects is to give you ample practice using a variety of C++ constructs in order to solve simple, yet fundamental, programming problems. Additionally, these projects will force you to think about issues related to program correctness, program testing, and techniques for debugging programs. It is my hope that these projects will also reveal to you the intricacies of constructing and maintaining relatively large software distributed in several files.

The task of understanding arithmetic expressions is a tiny part of what a compiler has to do in order to translate your program into machine code. So it is also my hope as you work on these projects you will get a glimpse into the workings of a compiler.

Input:

The input to your program is an arithmetic expression. As far as this project is concerned, an arithmetic expression can only include integers as operands and the operators + and *. Furthermore, no parentheses are allowed in arithmetic expressions. So for example:

 
3 + 8 * 234 + 892 * 4
11 * 2 * 3 + 8 * 9 * 1 * 8 + 8

are considered arithmetic expressions, while the following are not considered arithmetic expressions as far as this project is concerned:

 
(3+8) * 8 + (9+2)*8
3 + 3.8 + 9.23
3 - 8 + 2/10

The first line above is not an arithmetic expression because it contains parentheses; the second line is not an arithmetic expression because it contains real numbers as operands; the third line is not an arithmetic expression because it contains operators other than + and *. As stated earlier, you may assume that the input to your program is a valid arithmetic expression. In the input, between an operator and an operand that occur consecutively, there is at least one white space. Recall that a white space can be a blank (space) character, or an end of line character, or a tab character. Thus the input to your program may be spread across several lines or may appear in a single line. You may assume that after typing the last operand in the input arithmetic expression, the user will type the character Q to indicate the end of the arithmetic expression. The last operand and Q may be separated by one or more white spaces.

You can assume that the arithmetic expression in the input evaluates to an integer that is not too ``large''. In other words, you may assume that no arithmetic expression provided as input to your program will evaluate to an integer that overflows the memory set aside for an integer variable on your computer.

Output:

As output, your program should simply produce a message showing the value that the input arithmetic expression evaluates to. For example, if the input to your program is:

3 + 5 * 4 Q

then your program should produce the following output:

The expression evaluates to 23

No further output is necessary.

Processing the expression:

The heart of your program consists of a loop which processes the arithmetic expression until there are no more operators in the input stream. In each execution of the loop, an operator and the following operand are read and the value of the current expression is updated. More precisely, a sketch of the algorithm that you might use to process the arithmetic expression is as follows:

 
	 read first operand
	 assign the first operand to answer
	 while (more operators in the input stream)
	 {
		 read new operator
		 read new operand
		 update the answer using the new operator and new operand
	 }

The main details missing from the above algorithm relate to how the answer is updated based on the new operator and new operand. An incorrect way of updating answer is as follows:

 
	 if (new operator is "+")
		 answer = answer + value of new operand
	 if (new operator is "*")
		 answer = answer * value of new operand

The problem with the above way of updating answer is that it entirely ignores operator precedence. As you know, it is conventional to give the * operator higher precedence than the + operator. The implication is that an expression such as 3 + 5 * 4 evaluates to 23 and not 32 because the * operator is evaluated before the + operator. It is easy to verify that the above way of updating answer would cause 3 + 5 to be evaluated first followed by the evaluation of 8 * 4.

Your task therefore is to start with the above algorithm and modify it so that it respects arithmetic precedence. The key to this modification is realizing that the + operator cannot always be evaluated as soon as it is read. However, you should note that it is not necessary to read more than two operators before one can be evaluated.

Making your program readable:

A C++ program that fits within the guidelines described above and performs the desired task would be merely correct. I would like you to write programs that are not only correct, but are easy to read. Three ways of making your program easy to read are:

• Using a consistent indentation. The textbook follows a certain style of indentation and I follow a slightly different style. You can use any style you wish, provided it is consistent and not too crowded.

• Using comments liberally. Every function you use, should start with a ``header'', that is a block of comments that briefly explains the purpose of the function. You should also provide a brief comment for most variables or parameters your program uses. Just before a block of code that performs a single logical task, you should write comments specifying what the block of code does. For example, you should write comments before a while-loop or before a if-statement. You should also, at the beginning of your program, list any errors in your program or exceptions that the graders should be aware of. Also, in the block of comments at the beginning of the program, make sure that your name and your section number appear prominently.

• Using appropriate names for variables. The amount of time you spend thinking of and typing expressive variable names will be adequately compensated for by the fact that a program with expressive variable names is much easier to understand and modify.

• Trying to avoid convoluted logic. You will be graded on the simplicity of your logic and algorithms. While this is usually a subjective decision, for a program as small as this it is possible to devise fairly simple algorithms with very little effort. If you have any doubts about how complicated your code is, you should talk to the TAs or to me prior to submitting your program.

What to turn in:

Turn in a single 3.5'' Macintosh formatted disk with a single file called project1.cpp that contains your C++ program. If your program is on a PC formatted diskette, there is no need to reformat it for a Macintosh since Power Macintosh computers in MLH ITC can read PC formatted diskettes also. However, if you are a PC user you should make sure that your program compiles and executes within the CodeWarrior environment as well. All programs, independent of their origins, have to compile and execute within the CodeWarrior environment. Make sure that there is nothing else on your diskette. Clearly label your diskette by writing your name, section number, and the project number on it. In addition turn in a printout of your program.

A final word:

A programming project will alway take several times longer than you think it will. So please do not put this off till the last week. Start as early as possible; the TAs and I will be glad to help.