Electrical & Computer Engineering Department, University of Maryland, College Park

Integer Arithmetic Expression Evaluator

Project Objective:

1. get familiar with the process of completing a programming project.

2. learn how to use and manipulate arrays.

3. understand precedence and associative rules.

4. use program selection: if, if-else, switch statements.

5. use basic loops (while, do-while, for) for repetition.

Project Description:

In this project, you will design and implement a program to evaluate an arithmetic

expression. The arithmetic expression will contain only integers, both positive and negative, and

the following six basic binary operators +, -, %, /, *, and ^ as well as parentheses ().

Your program should read in the expression from an input file. The input file has a

specific format, which is described below. After reading the expression, you first will need to

evaluate all the negative operands in the expression; next you will evaluate the expression inside

the parentheses; followed by the power operator ^, then *, /, and % operators, and finally the

binary + and – operators. You will output the initial expression, intermediate steps, and the final

solution to an output file. A master program, in the format of executable file, and a sample input

file and output file will be provided.

Input

Your program will read in input from a file of multiple lines. Each line represents exactly

one arithmetic expression. The first two numbers of a line are the number of the operands, n

(2≤n≤10), and the number of the operators, m (n-1≤m≤20), in the expression. This is followed

by n operands of integer values, and then m operators with the following possible character

values (+,-,*,/,%,^,(,)). All the numbers and characters are separated by a single space, and there

are no superfluous spaces at the end of each line. For example, the following line of the input file

9 10 5 2 8 5 7 2 -5 1 -2 ^ + / + % * + ( + )

corresponds to the following 9-operand arithmetic expression

5 ^ 2 + 8 / 5 + 7 % 2 * -5 + (1 + -2)

Output

This project requires you to write your output to a file provided on the commander line.

Because you will be given an exact procedure to evaluate the arithmetic expressions, your Electrical & Computer Engineering Department, University of Maryland, College Park

Fall 2014 ENEE140 Dr. Gang Qu

program’s output should match EXACTLY the output from the master program. If there is a

mismatch, most likely there are mistakes somewhere in your code. Here is the procedure you

should follow to evaluate an expression. Using the same expression as in the previous example

1. The first thing you will do is to print out the initial expression that will be evaluated:

<space><space>5 ^ 2 + 8 / 5 + 7 % 2 * -5 + (1 + -2)

Note that there will be two empty spaces on the left before the first operand. Also note

that all operands/operators are separated by a single space, however, there is no space

between the negative sign (-) and the value of the negative numbers, e.g. -5 and –1; there

is also no space between the parentheses and the value, e.g. ( and 1, -2 and ).

2. Next, you will evaluate the negative numbers such that all operands will be non-negative

without changing the result of the expression, and print out the expression:

= 5 ^ 2 + 8 / 5 – 7 % 2 * 5 + (1 – 2)

Notice how the two + signs were changed to – signs due to the negative signs in –5 and –

2. Also notice that this line starts with an equal sign “=” and one space followed by the

first operand of the expression. This is to ensure the alignment of the partially evaluated

expressions with the initial expression. There is one exception to the rule: if the first

operand of the expression has to be negative, then it should keep the - sign.

If there is no negative operands, the expression should not be printed out again in this

step..

3. Now you will evaluate the portion of the expression that is inside the parentheses,

following the same precedence and associative rules as exampled in the items below. In

this example, your program should print out

= 5 ^ 2 + 8 / 5 – 7 % 2 * 5 + -1

Notice that now it is ok to have negative numbers (as the result of partial evaluation of

the expression). If there are multiple operators inside the parentheses, there should be

multiple lines of output, one after the evaluation of each operator (see below for more

examples on this). If there are multiple parentheses, they should be evaluated from LEFT

to RIGHT. If there are nested parentheses (bonus part), the one inside should be

evaluated first. (This part can be challenging and you need to think very carefully. It may

be a good idea to complete the other parts first (assuming there is no parentheses) and

then come back to add this feature.)

4. The operator that has the highest precedence is power ^. You are required to use a loop to

implement this (you are not allowed to use the power function in <math.h>) and print out

= 25 + 8 / 5 – 7 % 2 * 5 + -1 Electrical & Computer Engineering Department, University of Maryland, College Park

Fall 2014 ENEE140 Dr. Gang Qu

Notice that ^ happens to the first operator in this example, but even it is not, you should

first process ^. If there are multiple ^’s, you should evaluate the leftmost one first. The

two operands in the power operation will be positive, otherwise, you should print out an

error message, stop the evaluation of this expression, and move on to the next line in the

input file. Check the sample executable for the error message.

5. The operators with the next highest precedence are *, /, and %. You should evaluate them

one by one and from LEFT to RIGHT, and print out the intermediate result after the

evaluation of each operator. Note that / has both operands as integer and you should keep

the result as an integer as well. (for example, 8/5 = 1, not 1.60) Make sure you only do

one operator at a time and print out EVERY intermediate result.

= 25 + 8 / 5 – 7 % 2 * 5 + -1

= 25 + 1 – 7 % 2 * 5 + -1

= 25 + 1 – 1 * 5 + -1

= 25 + 1 – 5 + -1

If the second operand for / or % is 0 (for example 5 / 0 or -6 % 0), print out an error

message, stop the evaluation of this expression, and move on to the next line in the input

file. Check the sample executable for the error message.

6. Finally, you will evaluate the binary + and – operators, again from LEFT to RIGHT and

one at a time and print out the final value of the expression:

= 26 – 5 + -1

= 21 + -1

= 20

If everything goes well, this step will produce the final answer for the expression. Here is an

example of the complete output that you will print to the monitor as well as write on an

output file.

5 ^ 2 + 8 / 5 + 7 % 2 * -5 + (1 + -2)

= 5 ^ 2 + 8 / 5 – 7 % 2 * 5 + (1 – 2)

= 5 ^ 2 + 8 / 5 - 7 % 2 * 5 + -1

= 25 + 8 / 5 – 7 % 2 * 5 + -1

= 25 + 1 – 7 % 2 * 5 + –1

= 25 + 1 – 1 * 5 + –1

= 25 + 1 – 5 + –1

= 26 – 5 + –1

= 21 + -1

= 20

It is extremely important that you stick to the output and evaluation rules describes above. If

you follow the instructions exactly, your output should match the output from the master

program.

Electrical & Computer Engineering Department, University of Maryland, College Park

Fall 2014 ENEE140 Dr. Gang Qu

Project Requirements:

1. You must program using C under GLUE UNIX system and name your program p2.c.

2. Your program must be properly documented.

3. To be fair for those students who did not have priori programming experience, you can

only use the features and statements that we have covered in the lecture so far. Basic

command line arguments, variable declaration, file I/O, array, program selection, and

loop will be sufficient for this project. There will be penalty for using other features of C

(such as functions, multi-dimensional arrays, and any features in the string library).

4. submit the project (p2.c only) by (replace the ? in 010? by your own section number):

submit 2014 fall enee 140 010? 3 p2.c

5. Bonus: if you believe that you have found bugs in the master program, email Dr. Qu

(gangqu@umd.edu) and we will give bonus to the first person who has reported each bug.

A note about the bug and its fix will also be posted in the project Question and Answer

file. Depending on the nature of the bug and the difficulty to fix it, the bonus for each bug

will be 1-5 points. One student can receive up to 10 points for bonus.

There will also be a 5-point bonus on handling nested parentheses.

Grading Criteria:

Correctness: 85%

Good coding style and documentation: 15%

Bonus: nested parentheses 5%

finding bugs in the sample executable 10%

Late submission penalty:

submission within the first 24 hours after deadline -40%

submission after the first 24 hours after deadline: -100%

Program that does not compile under GLUE UNIX: -100%

Wrong file name (other than p2.c): -100%

Each feature/statement that are not allowed to use for this project: -20% Electrical & Computer Engineering Department, University of Maryland, College Park

Fall 2014 ENEE140 Dr. Gang Qu

-------------------------------------------------------------------- -

A programming template/outline just for your reference. It is by no

means a complete program or defines all the necessary variables. You

do not have to follow it.

#define SIZE 10 // maximal 10 integer operands for an expression

#define OP 20 // maximal 20 operators for an expression

int main(int argc, char * argv[])

{ declare variables that include at least the followings:

input/output files;

int array of size SIZE to store the operands;

char array of size OP to store the operators;

int operands=0; //number of operands in current line

int operators=0; // number of operators in current line

loop variables;

other variables to store useful information about the expression;

check argc == 3 or not;

open files with the safety check;

while(fscanf(input_file, “%d %d”, &operands, &operators)!=EOF)

{ read in the rest of the line and store the data;

print out the initial expression;

process all the negative operands and print out the expression;

// if you don’t know how to do this, skip for now and assuming

// all operands are positive. This is challenging.

process the partial expression inside the parentheses;

// if you don’t know how to do this, skip for now and assuming

// that there is no parentheses. This is also challenging.

process all the power ^; // remember to use loop and error message

process the %, *, and / operations; // remember error message

process the binary + and – operations;

}

close all files;

return 0;

}