Description

For this project, you’re going to write a program that can read numbers in either base 10 (like we normally do) or base 12 (like hexadecimal, but using decimal digits and letters X and E for 10 and 11, called dec and el). We will have two versions of our program, infix_10 will work with inputs and outputs in base 10 and infix_12 will work with base 12.

Both versions of the program will be able to evaluate arithmetic expressions involving five operators, plus, minus, times, exponent, and divide. Our program will evaluate the expression using precedence, then print out the result, or, if there is an overflow or a divide-by-zero while evaluating the expression, it will have a way to detect and report that.

The following shows an execution of the infix_10 program. After starting the program, the user enters an expression. The program reads the expression, evaluates it and reports the result

$ ./infix_10

35 + 2^2*30 / 47 – 62 * 49 / 34

-52

The following shows an execution of the infix_12 program instead. Just like the base 10 version of the program, the user enters an expression and then the program prints what it evaluates to. Below, the expression entered by the user is equivalent to the one above; it’s just in base 12 rather than base 10. For example, the first number, 2E, is a base 12 representation of the decimal number 35. You can check the decimal value by adding up the value of the digits: 2 * 12¹ + 11 * 12⁰ = 35.

$ ./infix_12

2E + 2^2*26 / 3E – 52 * 41 / 2X

-44

To help get you started, we’re providing you with a test script and several test inputs and expected outputs. There’s also a partial implementation of one of the header files you’ll be using. See the Getting Started section for instructions on how to set up your development environment so that you can be sure to submit everything needed when you’re done.

This project supports a number of our course objectives. See the Learning Outcomes section for a list.

Rules for Project 2

You get to complete this project individually. If you’re unsure of what’s permitted, have a look at the academic integrity guidelines in the course syllabus.

The requirements section explains what your program is supposed to be able to do. The design section describes some rules for how you’re going to build it. Be sure you follow these rules. It’s not enough to just turn in a working program; your program has to follow the design constraints we’ve asked you to follow. This helps to make sure you get some practice with the parts of the language we want to make sure you’ve seen. You should use material from lectures 1-7 to complete this assignment.

Requirements

Requirements are a way of describing what a program is supposed to be able to do. In software development, writing down and discussing requirements is a way for developers and customers to agree on the details of a system’s capabilities, often before coding has even begun. Here, we’re trying to demonstrate good software development practice by writing down requirements for our program, before we start talking about how we’re going to implement it.

Program Execution

The two versions of the program will be called infix_10 and infix_12. Like in the examples above, infix_10 will be a version compiled to read input numbers in base 10 and write results in base 10. The infix_12 version will read and write values in base 12 instead.

Input and Output

The infix programs will read a single line of text from standard input. The text will be an arithmetic expression consisting of numbers and the five arithmetic operators, +, -, *, ^ and /. The program is expected to respect the usual precedence of these operators, with ^ (exponentiation) having highest precedence, * and / (multiplication and division) having higher precedence than + and – (addition and subtraction), which have the lowest precedence. For example, given the following expression as input, the program will multiply 2 and 4 before adding their product to 3. There is an opportunity to add support for parentheses for extra credit.

3 + 2 * 4

The program should compute the value of the given expression and print it on a line by itself to standard output.

The program should be able to handle an arithmetic expression of arbitrary length. For example, it should be able to add up hundreds of individual numbers. The input expression is expected to end with a newline character,

and the program should exit after reading the first input line (ignoring any input after the first line). This behavior will make the program easier to use interactively. The user doesn’t have to signal the end-of-file condition to get the program to exit. It will automatically exit after the user enters a line.

Number Input and Representation

Input and output numbers will be given in either base 10 or base 12, depending on the version of the program.

The base 10 version will read and print numbers in base 10, like humans normally do, using decimal digits 0 .. 9.

The base 12 version of the program will use 0 … 9 for the first 10 digit symbols. It will use capital letter X to represent a digit value of 10 (called dec) and E for digit value 11 (called el). This is like what we do with hexadecimal; we’re just using fewer letters to get 12 different symbols.

For example, the following is a base 12 way of writing the (decimal) value 1000. The 6 symbol is worth 6 * 12². The E is worth 11 * 12¹ and the 4 symbol is worth 4 * 12⁰. Added together, these give us 1000 (in base 10).

6E4

The infix programs support signed values. Putting a – in front of a value indicates that it is negative. For a negative value, the hyphen must occur at the start of the number, without any spaces between it and the rest of the number. Also, numbers cannot have more than one hyphen in front; for example, you cannot represent a positive number as “–3”. The minus sign at the start of a number has higher precedence than any of the arithmetic operators, so, for example, -5^2 would be equivalent to (-5)^2 rather than -(5^2).

The value of an exponent must be non-negative. The base (the first argument) of ^ may be positive, negative or zero, but the second argument (the exponent) must not be negative. Any base (including zero) raised to the zero-th power should evaluate to 1. If the input expression uses a negative exponent, the infix program should terminate with an exit status of 103.

Operators at the same precedence associate left-to-right. So, for example, 5 + 2 – 1 would first add 5 and 2, then it would subtract 1 from the result. So, it would be equivalent to ( 5 + 2 ) – 1. The same is true for the exponentiation operator, so 2 ^ 3 ^ 4 would be evaluated like (2 ^ 3 ) ^ 4.

Internally, our program will represent values in the expression using the signed long type. So, it will really be representing values in binary, two’s complement, no matter what base is being used for input and output. On the common platform, this will let us represent values from -9223372036854775808 (LONG_MIN) up to 9223372036854775807 (LONG_MAX).

Expression Syntax

An expression consists of one or more numbers with arithmetic operators (+, -, *, ^ and /) in between them. Each expression should be given on a single line, with a newline character (\n) at the end.

Input numbers and operators may be separated (and preceded and followed) by any amount of whitespace, including spaces, tab characters (\t), carriage returns (\r), vertical tabs (\v) and form feeds (\f). Normally, whitespace would include newline characters, but we’re depending on newline to mark the end of an expression, so we won’t permit it within an expression.

Overflow and Divide-by-Zero

If the program ever gets a value that’s outside the range of a signed long, it should terminate with an exit status of 100, without printing any output. This could happen if one of the input values is too large or if one of the computations while evaluating the expression yields a number that’s too big (either as the final result of the expression or as one of the intermediate results).

If the expression includes an attempt to divide by zero, the program should terminate immediately with an exit status of 101.

Invalid Input

If input is invalid, your program should terminate with an exit status of 102, without printing any output. Input numbers must consist only of legal symbols for the base. That’s digits 0 … 9 for the base 10 program and digits 0 .. 9 and letters X, E for the base 12 version. Numbers may have a hyphen at the start indicating a negative value. Characters other than the five operator symbols and whitespace also can’t occur between numbers, and the input expression must have a newline at the end. If the input doesn’t satisfy these conditions, then it’s invalid.

If you do the extra credit, then your program should also permit parentheses in the input. If you don’t do the extra credit, you should consider an input expression to be invalid if it contains parentheses.

Design

The program will be implemented using three components. Here’s what they are responsible for:

operation.h / operation.c

This component provides functions for performing the five arithmetic operations on signed long values. They automatically detect overflow or divide-by-zero.

number.h / number_10.c / number_12.c

This component reads numeric values from input and writes results to output. It has two implementations, number_10.c for numbers written in base 10 and number_12.c for numbers written in base 12. It just has one header file since these two implementations both offer the same interface. We can use either one of these implementation files and the rest of the program will still operate the same.

infix.c

This is the top-level component, containing the main() function. With help from the other components, it is responsible for reading and evaluating the whole expression and printing the result.

The following figure shows the dependency structure of our components. The figure on the left shows the infix_10 program and the one on the right is the same figure for infix_12. The only difference is which implementation file we’re using for the number component. You can see we’ve tried to make sure there are no dependency cycles among the components. The operation component doesn’t need to use either of the other two components. The number component can use operation, and the top-level, infix component will use both of the other two.

Figure: dependencies among the program’s components

These two figures show how we’re going to build the two different versions of our program. They will both have an operation component, a number component and a infix component. The base 10 version of the program is linked with the object file for number_10.c, so it gets the versions of parse_value() and print_value() that are written for base 10. The base 12 version gets linked with the object file for number_12.c, so it gets the version of these functions for base 12.

Required Functions

You can use as many functions as you want to solve this problem, but you’ll need to implement and use a few functions that we’re asking you to create. Your operation.c component should have at least the following functions:

long plus( long a, long b )

This function adds the given parameters and returns the result. You wouldn’t normally need a whole function to do this for you, but the real job of this function is to automatically detect overflow. If the result of the addition is outside the range for a signed long, the function will detect the overflow and terminate the program with the correct exit status.

long minus( long a, long b )

This function is like plus(). It subtracts b from a and detects when overflow occurs.

long times( long a, long b )

This function is like plus(). It multiplies the parameters and detects overflow.

long exponential( long a, long b )

This function is like times(). It exponentiates the parameters (raises a to the power b if b is non-negative) and detects overflow.

long divide( long a, long b )

This function divides a by b and returns the result. It detects any attempt to divide by zero and terminates the program with the correct exits status when that happens. It also needs to detect one possible case of overflow during division.

The number_10.c and number_12.c implementation files will define the same functions. They both should define at least the following three functions. The parse_value() and print_value() functions will be implemented differently between the two components, but the skip_space() function will be identical. That means you will need to duplicate code for this function in two different implementation files. In general, duplicate code is something to avoid, but it’s OK for this part of the assignment.

int skip_space()

This function reads characters from standard input. It keeps reading characters until it reaches a nonwhitespace character or EOF. It returns the code for the first non-whitespace character it finds (or EOF). For this function, whitespace does not include the newline character. Code inside the number component or elsewhere in the program can use this to easily skip past whitespace within an expression.

long parse_value()

This function reads the next number from the input. In the number_10.c file, it will read a number in base 10; the implementation in number_12.c will try to read a number in base 12. If it detects errors in the input number, it terminates the program with the appropriate exit status.

void print_value( long val )

This function prints the given val to standard output. The implementation in number_10.c will print the number in base 10, while the number_12.c implementation will print it in base 12.

The infix.c component will contain main() and the following functions. There’s more detail on how the parser is expected to work in the “Parsing Numeric Expressions” section below.

static long parse_exp()

This function reads the highest-precedence parts of an expression, either an individual number (like “253”) or a sequence of numbers with the exponentiation operator in between them (like “2^5^3”). We’ll call these the factors in the input expression. Each time you call it, it will read the next factor and return the value it evaluates to. For example, if it reads 253, it will return the value 253. Or, if it reads 2^5^3, it will return 32768. This function will use parse_value() to parse the number(s) in each factor. You can see that we’ve marked this function as static. This prevents it from being used by other components. As mentioned in the style guide, it’s a good idea to mark functions as static if they are for internal use only in a component. The non-static functions should have a prototype in the header, so other components can use them. The static functions should not have a prototype in the header.

static long parse_mul_div()

This function reads the terms in the input expression. We’ll say a term is a sequence of one or more factors with multiply and/or divide operators in between them (like “5 * 3” or “2^3 * 3^5 / -4^2”). Each time you call it, it will use parse_exp() to parse the factors in the term. It will return the value its input term evaluates to. For example, it would return 15 if it read the term “5 * 3”; it would return 121 if it read the term “2^3 * 3^5 / -4^2” from the input. A term could contain just one factor, without any multiply or divide operator after it. In this case, parse_mul_div() would just return value of that factor.

Detecting Overflow

In class, we talked about a couple of ways to detect overflow when adding or subtracting numbers in two’s complement. For this program, you should detect overflow in plus() and minus() based on looking at the signs of the two operands vs the sign of the result. For example, if you add two positive numbers, the result should be positive. If you get a negative result, then an overflow must have occurred. There are some other cases you’ll need to consider to catch all possible overflows for addition and subtraction. You should be able to figure out these other cases and implement them in your operation.c component.

Catching overflows in multiplication is a little more interesting. We can’t just look at the signs of the operands vs. the sign of the result. Instead, we’ll check to make sure the product will be in range before we even perform the multiply. Consider the following statement, where a, b and c are all signed long.

c = a * b;

If a and b are both positive, then their product will be positive. If that product is larger than LONG_MAX, then we have an overflow. Before even multiplying a and b, we can figure out the largest value x such that x * b is less than or equal LONG_MAX. We just have to compute x = LONG_MAX / b. Integer division rounds down (toward zero), so, with x computed like this, x * b could be smaller than LONG_MAX. If LONG_MAX is evenly divisible by b, then x * b will be equal to LONG_MAX. Either way, x is the largest value that we can multiply by b without exceeding LONG_MAX. So, if a > x, then a is too large; a * b will overflow.

This gives us a way to test for overflow on multiplication when the two operands are both positive. As part of this project, you’ll need to come up with similar tests for the three other cases, when either a or b or both are negative. Remember that LONG_MAX is the largest positive number that a signed long can store, but LONG_MIN is the smallest negative value. You’ll need to consider this when either a or b (but not both) are negative. Also, remember that division truncates for positive or negative values (it rounds toward zero).

Exponentiation should be handled as repeated multiplication. This allows the overflow detection built into your times() function to help you detect overflow when exponentiating a value.

Parsing Numeric Expressions

Your top-level component, infix.c will be responsible for reading arithmetic expressions and evaluating them

(with help from the other two components). An expression is a number, possibly followed by an operator and another number, possibly followed by another operator and number, and so on. If we didn’t need to worry about precedence, we could just parse an expression with a while loop, reading operators and numbers until we reached the end-of-line.

The main function will be responsible for some of the parsing, but we will use two additional functions to help parse the input expression in a way that respects the precedence. We’ll say a factor is either a single number in the input expression or a series of numbers with the exponentiation operator in between. For example, “253” would be a factor, or “25^3” or “2^5^3”. These are the highest precedence parts of an expression. The function, parse_exp(), will be responsible for parsing these parts of an expression from the input and returning the value they evaluate to. If there’s an overflow while computing the value of these sub-expressions, or some other type of error, this function may terminate the program with an error code (e.g., 103 for a bad exponent), without ever returning.

We’ll say that a term is a sequence of one or more factors with multiply or divide operators in between them. So, for example, “2” would be a (trivial) term, or “2 * 3” or “2^2 * 3^3 / 4”. These are the parts of the input expression at the second-highest level of precedence. The parse_mul_div() function will have the job of parsing terms in the input expression. When called, it will read in the next term and return whatever it evaluates to. If the input expression contains an error (e.g., if it produces an overflow or a divide-by-zero), the program may terminate in parse_mul_div() without returning.

The main() function will be responsible for parsing the lowest-precedence parts of the input expression. It will read the expression as a sequence of terms (each one parsed by parse_mul_div()) with plus or minus operators in between. It will compute the value of the expression and then print the result at the end.

This organization of the code is typical of how parts of a program might be parsed by the compiler (in what’s called a recursive-descent parser). We can define functions for parsing parts of the input, with each level of precedence handled by a different function.

The following figure shows how your code would parse a simple input expression. The input is a sequence of one or more terms, so the main() function will call parse_mul_div() to read and evaluate the first term. Inside parse_mul_div(), a term consists of one or more factors, so parse_mul_div() will call parse_exp() to read the first factor. The parse_exp() function calls parse_value() to read an integer (35). Since the 35 isn’t followed by an exponentiation operator, parse_exp() returns 35 as the value of the first factor.

Figure: While reading the first term, parse_mul_div() calls parse_exp() to read the first factor

After the first factor, parse_mul_div() sees the multiplication operator, so the term must contain another factor. It calls parse_exp() to read the next factor. Inside parse_exp(), the first number (2) is followed by the exponentiation operator, so it reads the next number and returns 4 as the value of the term.

Figure: parse_mul_div() uses parse_exp() to read the second factor in the expression.

The parse_mul_div() sees a division operator after the second factor, so there must be another factor in the term. It calls parse_exp() to read it. That’s the last factor in the term, so it returns the value of the first term, 35 * 4 / 30 = 4.

Figure: parse_mul_div() continues calling parse_exp() to read each successive factor until it reaches the end of the term.

There’s a plus operator after the first term, so main() knows there must be another term. It calls parse_mul_div() again to read the next term. The parse_mul_div() function calls parse_exp(), which calls parse_value(). After getting the number 47, there’s no exponentiation operator, so this factor must just contain a number; parse_exp() can just return the value 47. There’s no multiply or divide after the 47, so this term must just contain one factor. The parse_mul_div() function can just return the value 47. Back in main(), the value of the second term can be subtracted from the value, 4, from the first term, giving us a total of -43 for the first two terms.

Figure: The second term in the input just contains one factor.

The main() function will see a plus operator after the second term, so there must be another term. It can call parse_mul_div() to read this term. The parse_mul_div() function will call parse_exp() to read each of the factors in this term and eventually return the resulting product or quotient. Back in main, this can be added to the difference from the previous two terms to get the value of the whole expression (-5).

Figure: This shows what parts of the input are parsed by each of the parsing functions.

Be sure to have a look at the ungetc() function described below. This can be helpful in writing your parsing code. It lets you effectively back up by a character if you read more input than you need and need to put a character back on the input stream (so other parts of the parsing code can read that character). For example, parse_mul_div() will need to read ahead, to see what the next operator is after a factor. If it’s a multiply or a divide operator, it will need to read another factor. If it’s a plus or minus, it will need to return to main() and let main() read the next operator. If parse_mul_div() already read this next operator, it will need to put it back on the input stream, so main() can read it instead.

Reading and Writing Numbers

Your number_10.c and number_12.c files will each implement functions for reading and writing numbers. For the implementations in number_10.c, printing numbers will be easy. You can print them in base 10 using printf() with the “%ld” conversion specifier. For reading numbers in either base or for printing numbers in base 12, you will need to write your own parsing and printing code. The following describes how to read and print numbers in base 12. For reading them in base 10, you can implement a similar technique to your base 12 parsing code. It will be a little bit easier than the base 12 example, since numbers won’t contain any letters.

Note that since the scanf() function doesn’t provide a good way to detect overflow in numeric input, you won’t be able to use scanf() to read numbers, not even in base 10. You can use scanf() temporarily, as you start developing your implementation. That will make the number_10.c file easier to write, but you will need to switch to your own number parsing code before you turn in the project.

To read numbers in base 12, we’ll use a technique based on Horner’s rule. It will make it easy to read numbers from left to right. The following pseudo-code describes how the algorithm works. You’ll need to add code to handle negative values (with a hyphen character in front). You’ll also need to add your own code to detect errors while reading and exit appropriately.

// Value we’ve parsed so far.   value = 0;

// Get the next input character.

ch = next_input_char();

// Keep reading as long as we’re seeing digits.

while ( ch is a digit in base 12 ) {

// Convert from ASCII code for the next digit into the value

// of that digit.  For example ‘X’ -> 10 or ‘7’ -> 7     d = char_to_digit( ch );

 

// Slide all digits we’ve read so far one place value to the

// left.

value = value * 12;

// Add this digit as a new, low-order digit.

value = value + d;

 

// Get the next input character.

ch = next_input_char();   }

// ch was one character past the end of the number.  Put it back on

// the input stream so it’s there for other code to parse (see notes

// below about ungetc()).   unget( ch );

There’s a possibility of overflow as you’re parsing a number. This could happen either while you’re multiplying by 12 or adding in the new low-order digit. You could add code here to detect overflow, or you could just use the functions from your operation.c component to perform the multiply and the add; they already detect overflow and exit the program appropriately if it happens.

In class, we looked at a technique for converting between base 10 and binary. Your number_12.c implementation will use a similar technique to print out results in base 12. Pseudo-code for this technique is shown below, where value is the value we’re supposed to print.

// While there are more digits to print.

while ( value != 0 ) {

// Get the next digit on the right.

d = value % 12;

 

// Convert it to a character, e.g, 11 -> ‘E’ or 3 -> ‘3’     ch = digit_to_char( d );

 

// Print out the next digit (note, this will give us the digits

// backward).     print( ch );

// Slide remaining digits to the right.     value = value / 12;   }

You’ll need to make some changes to this code to get it to work in you program. In particular, you’ll need to:

Add support for negative numbers (e.g., printing a hyphen in front).

The code above won’t print anything if value is zero. That’s easy to fix by handling zero as a special case.

The code above will print the digits backward. It gets the low-order digit first and ends with the high-order digit. If we knew how to work with strings, this would be easy to fix. We could just save all the digits and then print them in reverse. Instead, we’ll fix the digit ordering using recursion. You can implement the procedure above recursively instead of iteratively. On each recursive call, you can extract (but don’t print) the low-order digit, make a recursive call to print the remaining, high-order digits, then print the low-order digit you extracted. This should give you the digits with the high-order one first.

Ungetting Characters

If you just read the character, ch from standard input, you can call ungetc() to put that character back onto the input stream. This won’t put another copy of the character back on the terminal or anything like that. It will just put it back in the input buffer for standard input, to be read again later.

During parsing, it can be convenient to put a character back onto a stream. For example, if you’re reading a number from input, you’ll need to read characters until you reach the end of the number. This generally requires you to read the next character past the end of the number itself. Other parts of your parsing code may be responsible for reading this next character and using it (e.g., if it’s an operator like ‘+’ or ‘*’). The ungetc() function lets you put this character back onto the stream so it can later be read by other parts of your program.

Calling ungetc() as follows will put the given character, ch back onto the standard input stream.

ungetc( ch, stdin );

Globals and Magic Numbers

You must complete this project without creating any global variables. The function parameters give each function everything it needs.

Avoid magic numbers in your source code. Use the preprocessor to give a meaningful name to all the important, non-obvious values you need to use.

Extra Credit

Our infix programs are not required to support parentheses. They just evaluate a given expression with the usual precedence for operators. For up to 10 points of extra credit, you can add support for parentheses. With the extra credit, your program should be able to evaluate expressions like the following. Here, it will perform the addition and subtraction before exponentiation and subsequently multiplying the results.

( 5 + 8 ) * ( 7 – 2 ) ^ 2

Like the other parts of the expression, parentheses can have whitespace before or after them. As usual, an expression inside parentheses can appear in place of any number in the input. The entire input expression could even be inside parentheses.

The starter has four sample inputs and expected output files for the extra credit option. These are named like input-ec-*-*.txt and expected-ec-*-*.txt. The input-ec-12-2.txt file is an error test. The parentheses don’t match, so the program should terminate with an exit status of 102.

Build Automation

You get to implement your own Makefile for this project. We’re expecting it to be called “Makefile”, with a capital M at the start and no filename extension at the end. This Makefile will be a little more interesting than usual, since we’ll be compiling two versions of our program, one for base 10 and the other for base 12.

Your Makefile should be smart enough to separately create each of the object files needed by your program. It should have a separate rule to create an object file by compiling the corresponding implementation file. It will also have a rule to build each of the two executables. One rule will be for linking together infix.o, number_10.o and operation.o to create the infix_10 executable. The other will link together infix.o, number_12.o and operation.o to create the infix_12 executable. When it’s creating an object file, your Makefile should use the usual compile-time flags, -Wall, -std=c99, and -g. When you’re linking, you will need to use the -o flag to specify the name of the executable you want to create. You won’t need any other flags for the linker. For example, you won’t need the -lm flag since we won’t be using the math library for this project.

From class, you’ll remember that make includes default rules for building common types of targets. You can use these built-in rules for the compile steps if you want. If you do use the built-in rules, be sure to set up variables like CFLAGS so your code compiles with the options we need. Also, you will need to write your own gcc commands for the linking steps in your Makefile. The built-in rules won’t work for this since the executable name doesn’t match the names of your source files.

To use this Makefile, you can tell it the specific target you want it to build. For example, if you run it as follows, it will create the infix_10 program, compiling any needed prerequisites first, then linking them together into an executable.

$ make infix_10

To get it to build the infix_12 program, you can just run make with infix_12 on the command line instead. The testing script runs make this way to build each version of you program before testing it.

The Makefile should also have a rule with the word clean as the target. This will let the user easily delete any temporary files that can be rebuilt the next time make is run (e.g., the object files, executables and any temporary output files).

A clean rule can look like the following. It doesn’t have any prerequisites, so it’s only run when it’s explicitly specified on the command-line as a target. It doesn’t actually build anything; it just runs a sequence of shell commands to clean up the project workspace. In the example below, we used the <tab> notation to remind you where the hard tabs need to go in a Makefile. Don’t actually put <tab>; use a real tab character instead. You can see that this rule runs commands to delete temporary files from the project workspace directory. In your clean rule, replace things like all-your-object-files with a list of the object files that get built as part of your project. clean:

<tab>rm -f all-your-object-files

<tab>rm -f your-executable-programs

<tab>rm -f any-temporary-output-files

<tab>rm -f anything-else-that-doesn’t-need-to-go-in-your-repo

To use your clean target, type the following at the command line, but first be sure you have committed all of the files that you need to your github repo. If you make a mistake in this rule, you could accidentally delete some of your files. Committing them to your repo first can help make sure you don’t lose anything important. You can always recover your files from your repository if something goes wrong.

$ make clean

You may want to add a rule like the following one as the first rule in your Makefile. Remember that the first rule is the default rule, if you don’t specify a particular target to build. This rule says if you’re building all (the default target since it’s the first rule), then you need to first build the infix_10 and infix_12 targets. This will get make to try to build both versions of your program whenever you just enter the make command.

all: infix_10 infix_12

Selective Rebuilding

Your Makefile should correctly describe the project’s dependencies, so targets can be rebuilt selectively, based on what source files have changed since the last time their target was built. The following figure tries to show how the various files in your project depend on each other. It illustrates the infix_10 program, but a similar figure could be made for infix_12.

Figure: Dependency structure for source files and make targets

The arrows show where one file depends on another. The blue and green bloxes represent source files and the red ones show object files that your Makefile knows how to build. The exeuctable at the bottom is what the makefile builds from all the objects.

If none of the targets have been built (e.g., if you just ran make clean), then your Makefile will have to rebuild all the targets. Running “make infix_10” should produce output like the following. The order of the compile steps may be different, but you should see each of your implementation files being compiled to an object file, then you should see a gcc command for linking you object files into an executable.

$ make infix_10

gcc -g -Wall -std=c99   -c -o infix.o infix.c gcc -c -Wall -std=c99 -g number_10.c -o number_10.o gcc -g -Wall -std=c99   -c -o operation.o operation.c gcc infix.o number_10.o operation.o -o infix_10

After building your project once, make should be smart enough to avoid unnecessary steps on subsequent builds. If you try to run make again without changing anything, it should tell you there’s nothing to rebuild:

$ make infix_10 make: ‘infix_10’ is up to date.

If you modify just some of your source file, the dependencies in your Makefile should let make figure out what targets need to be rebuilt. For example, if you change just the number_10.c source file and then rebuild only the object file for number_10 and the executable, infix_10 have to be rebuilt. From the figure above, you can see that these are the only files that depend on this source file. You can try this out by making a small edit to your number_10.c file then saving it, or you can use the touch command to make the computer think the file has been modified without having to actually edit it.

$ make infix_10

gcc -c -Wall -std=c99 -g number_10.c -o number_10.o gcc infix.o number_10.o operation.o -o infix_10

However, if you change the header file, number.h, make will have to rebuild both the number_10.o object file and the infix.o object file. The source files for both of these components include the number.h header. After rebuilding these two objects, it will have to link all the objects into an executable:

make infix_10

gcc -g -Wall -std=c99   -c -o infix.o infix.c gcc -c -Wall -std=c99 -g number_10.c -o number_10.o gcc infix.o number_10.o operation.o -o infix_10

Testing

The starter includes a test script, along with test input files and expected outputs for each version of the program. When we grade your programs, we’ll test it with this script, along with a few other test inputs we’re not giving you.

To run the automated test script, you should be able to enter the following commands. The first one sets the script to be executable; you probably just need to do this once for the first time you run it.

$ chmod +x test.sh # probably just need to do this once $ ./test.sh

The test script will try to build both versions of your program using your Makefile. Then, it will see how they behave on all the provided test inputs described below. The test script is what’s called a shell script. It contains the same kinds of command you type at the terminal when you’re working on a Unix machine.

You probably won’t pass all the tests the first time. In fact, until you have a working Makefile, you won’t be able to use the test script at all.

If you want to compile one of your programs by hand, the following command should do the job. Here, we’re compiling and linking three source files into an executable that uses base 10. Your Makefile should be smarter than this, compiling each source file individually and then linking all the resulting objects together, rather than compiling and linking everything all at once.

$ gcc -Wall -std=c99 -g infix.c number_10.c operation.c -o infix_10

The following command is like the one above, but it tries to build he infix_12 version of the program instead.

$ gcc -Wall -std=c99 -g infix.c number_12.c operation.c -o infix_12

To run your program, you can do something like the following. The test script prints out how it’s running your program for each test case, so this should make it easy to check on individual test cases you’re having trouble with. The following commands run the infix_10 program with input read from input-10-08.txt and with output written to the file, output.txt. Then, we check the exit status to make sure the program exited successfully (it should for this particular test case). Finally, we use diff to make sure the output we got looks exactly like the expected output for test case 8.

$ ./infix_10 < input-10-08.txt > output.txt

$ echo $?

0

$ diff output.txt expected-10-08.txt

If your program generated the correct output, diff shouldn’t report anything. If your output isn’t exactly right, diff will tell you where it sees differences.

Test Input Files

With the starter, we’re providing a number of test inputs for trying out your programs. Some are for the base 10 version of the program and some are for the base 12 version. The automated test script, test.sh uses your Makefile to build both versions of your program. Then, it runs it on the provided test cases. The following tests are for infix_10. Input files for these tests are named like input-10-*.txt and the expected output files are named expected-10-*.txt.

1. Read the number 1 from input and then report it as the result.
2. Adding two single-digit numbers, without any extra space.
3. A subtraction problem with some extra space.
4. A sequence of add and subtract operations with various three-digit positive and negative values.
5. Multiplying two numbers. This input has some extra characters after the first line. This isn’t an error; it should be ignored by the program. We only care about input up to the first newline character.
6. A division problem with a lot of extra space.
7. Several multiply and division operations including positive and negative numbers.
8. An expression including the four operations. This is the example shown at the start of the assignment. You will need to have precedence working to pass this test.
9. A multiplication problem, one that’s too large for an int, but within the capacity of a long.
10. A division problem, without any spaces between the operator and operands (which is OK).
11. This test adds the largest negative value and the largest positive values.
12. This is an error test, it has an overflow in an addition operation.
13. This is an error test. it includes an invalid expression, with two operators in a row.
14. This is an error test. It includes a divide-by-zero.
15. An exponent test
16. An overflowing exponent test

The following tests are provided for the infix_12 version of the program. For these tests, the input files are named like input-12-*.txt and the expected output files are named expected-12-*.txt.

1. This reads the number 1 from input and reports it as the result.
2. This reads the number EEE (the largest three-digit number we can input) and then adds 1 to it.
3. This does some addition and subtraction operations on positive and negative numbers.
4. An expression including all four operations. This is the base 12 example shown at the start of the assignment.
5. A problem that evaluates to zero.
6. This test adds up three numbers to get the largest positive number that can be stored in a signed long.
7. This test multiplies two numbers to get the largest negative number a signed long can hold.
8. This is an error test. it includes an input number with an invalid digit.
9. This is an error test. One of the input numbers is too large to fit in a signed long.
10. This is an error test. It multiplies two negative numbers to get a positive number that’s too large to represent.
11. This is an error test. There’s a symbol in between two numbers that isn’t a valid operator.

Keep in mind, when we’re grading your programs, we’ll test them on these tests and on a few other tests that we’re not providing. This is a good reason to think about possible tests or inputs that aren’t done by the test.sh program.

Grading

The grade for your project will depend mostly on how well your code functions on test cases. We’ll also expect your code to compile cleanly, we’ll expect it to to follow the style guide and the expected design, and we’ll expect a working Makefile.

Working Makefile, including dependencies and a make clean rule: 10 points

Compiling cleanly on the common platform: 10 points

Correct behavior on all test cases: 80 points

Source code follows the style guide: 20 points

Support for parentheses: 10 extra credit points

Deductions

Up to -50 percent for not following the required design.

Up to -30 percent for failing to submit required files, submitting files with the wrong name or having extraneous files in the repo.

Up to -20 percent penalty for late submission within 48 hours.

Getting Started

To get started on this project, you’ll need to clone your NCSU github repo and unpack the given starter into the p2 directory of your repo. You’ll submit by committing files to your repo and pushing the changes back up to the NCSU github.

Cloning your Repository

Everyone in CSC 230 has been assigned their own NCSU GitHub repository to be used during the semester. It already has subdirectories (mostly empty) for working on each of the remaining projects. How do do you figure out what repo you’ve been assigned? Use a web browser to visit github.ncsu.edu. After authenticating, you should see a drop-down menu over in the upper-left, probably with your unity ID on it. Select “engr-csc230spring2023” from this drop-down and you should see a repo named something like “engr-csc230spring2023/unity-id” in the box labeled Repositories over on the left. This is your repo for submitting projects.

I’ve had some students in the past who do not see the organization name, “engr-csc230-spring2023” in their drop-down menu. I’m not sure why that happened, but when they chose “Manage organizations” near the bottom of this drop-down, it took them to a list of all their repos, and that list did include “engr-csc230spring2023”. Clicking on the organization name from there took them to a page that listed their repo. If you’re having this problem, try the “Manage organizations” link.

You will need to start by cloning this repository to a place where you’d like to work, say a subdirectory in your AFS file space. You should be able to do this with the following command (where unity-id is your unity ID, just like it appears in your repo name):

$ git clone https://[email protected]/engr-csc230-spring2023/unity-id.git

This will create a directory with your repo’s name. If you cd into the directory, you should see directories for each of the projects for the class. You’ll want to do your development for this assignment right under the p2 directory. That’s where we’ll expect to find your project files when we’re grading.

Unpack the starter into your cloned repo

You will need to copy and unpack the project 2 starter. We’re providing this file as a compressed tar archive, starter2.tgz. You can get a copy of the starter by using the link in this document. Temporarily, put your copy of the starter in the p2 directory of your cloned repo. Then, you should be able to unpack it with the following command:

$ tar xzvpf starter2.tgz

Once you start working on the project, be sure you don’t accidentally commit the starter archive to your repo (that would be an example of an extraneous file that doesn’t need to be there). After you’ve successfully unpacked it, you may want to delete the starter from your p2 directory, or move it out of your repo.

$ rm starter2.tgz

Instructions for Submission

If you’ve set up your repository properly, pushing your changes to your assigned CSC 230 repository should be all that’s required for submission. When you’re done, we’re expecting your repo to contain the following files. You can use the web interface on github.ncsu.edu to confirm that the right versions of all your files made it.

infix.c : Top-level component for your calculator program.

number_10.c / number_12.c / number.h : Implementation and header file for the component that reads and writes numbers in the chosen base.

operation.c / operation.h : Implementation and header file for the component that performs arithmetic operations.

Makefile : Makefile for efficiently building both versions of your program, infix_10 and infix_12. input-10-*.txt : Test input files for the base 10 version of the program, provided with the starter. input-12-*.txt : Test input files for the base 12 version of the program, provided with the starter.

expected-10-*.txt : Expected image output files for the base 10 version of the program, provided with the starter. expected-12-*.txt : Expected image output files for the base 12 version of the program, provided with the starter. test.sh : test script, provided with the starter.

.gitignore : a file for this project, telling git some files to not commit to the repo.

Pushing your Changes

To submit your solution, you’ll need to first commit your changes to your local, cloned copy of your repository. First, you need to add any new files you’ve created to the index. Running the following command will stage the current versions of a file in the index. Just replace the some-file-name with the name of the new file you want commit. You only need to do this once for each new file. The -am option used with the commit below will tell git to automatically commit modified files that are already being tracked.

$ git add some-file-name

When you’re adding new files to your repo, you can use the shell wildcard character to match multiple, similar filenames. For example, the following will add all files ending with a .c extension to your repo.

$ git add *.c

When you start your project, don’t forget to add the .gitignore file to your repo. Since its name starts with a period, it’s considered a hidden file. Commands like ls won’t show this file automatically, so it might be easy to forget.

$ git add .gitignore

Before you commit, you may want to run the git status command. This will report on any files you are about to commit, along with other modified files that haven’t been added to the index yet.

$ git status

Once you’re ready to commit, run the following command to commit changes to your local repository. The -am option tells git to automatically commit any tracked files that have been modified (that’s the a part of the option) and that you want to give a commit message right on the command line instead of starting up a text editor to write it (that’s the m part of the option).

$ git commit -am “<a meaningful message about what you’re committing>”

Beware, you haven’t actually submitted anything for grading yet; you’ve just put these changes in your local git repo. To push changes up to your repo on github.ncsu.edu, you need to use the push command:

$ git push

You should plan to commit and push often as you develop your project, whenever you finish making a significant change to your work. This will help to show that you’re working on the project. Whenever you’ve made a set of changes you’re happy with, you can run the following to update your submission.

$ git add any-new-files

$ git status

$ git commit -am “<a meaningful message about what you’re committing>”

$ git push

Keeping your repo clean

Be careful not to commit files that don’t need to be part of your repo. Temporary files or files that can be easily re-generated will just take up space and obscure what’s really changing as you modify your source code. And, the NCSU github site puts a file size limit on what you can push to your repo. Adding files you don’t really need could create a problem for you later.

The .gitignore file helps with this, but it’s always a good idea to check with git status before you commit, to make sure you’re getting what you expect.

Checking Jenkins Feedback

We have created a Jenkins build job for your project. it’s only available from on campus, so if you want to check your Jenkins results from off-campus, you’ll need to VPN into a campus address first. If you’ve never used VPN before, you’ll find instructions for setting it up and connecting at: https://oit.ncsu.edu/campus-it/campus-datanetwork/vpn/. Follow the instructions for your type of system and get connected to the campus network. It will take a little bit of work to get this configured, but it will pay off in later classes if you already know how to use VPN.

Jenkins is a continuous integration server that is used by industry to automatically build and test applications as they are being developed. We’ll be doing the same thing with your project as you push changes to the NCSU github. This will provide early feedback on the quality of your work and your progress toward completing the assignment.

The Jenkins job associated with your GitHub repository will poll GitHub every two minutes for changes. After you have pushed code to GitHub, Jenkins will notice the change and automatically start a build process on your code. The following actions will occur:

Code will be pulled from your GitHub repository

A testing script will be run to make sure you submitted all of the required files, to check your code against parts of the course style guidelines and to try out your solution on each of our provided test cases

Jenkins will record the results of each execution. To obtain your Jenkins feedback, do the following tasks (remember, after a push, you may have to wait a couple of minutes for the latest results to appear):

Go to Jenkins for CSC230. Your web browser will probably complain that this site doesn’t have a valid certificate. That’s OK. Tell your browser to make an exception for this site and it should let you continue to the site.

You’ll need to authenticate with your unity ID and password.

Click the project named p2-unityid

There will be a table called Build History in the lower left, click the link for the latest build

Click the Console Output link in the left menu (4th item)

The console output provides the feedback from compiling your program and executing the provided test cases. If the bottom of the output says you failed some tests, there should be one or more lines earlier in the output that starts with four stars. These should say something about what parts of the test your program failed on.

Succeeding on Project 2

Be sure to follow the style guidelines and make sure your program compiles cleanly on the common platform with the required compile options. If you have your program producing the right output, it should be easy to clean up little problems with style or warnings from the compiler.

Be sure your files are named correctly, including capitalization. We’ll have to charge you a few points if you submit something with the wrong name, and we have to rename it to evaluate your work.

We’ll test your submission with a few extra test cases when we’re grading it. Maybe try to think about sneaky test cases we might try, like behaviors that are described in this write-up but not actually tested in any of the provided test cases. You might be able to write up a simple test case to try these out yourself.

There is a 48 hour window for late submissions. If you submit late up to 24 hours after the due date, you will receive a 10% penalty. If you submit 25-48 hours late, you will receive a 20% penalty. Use this if you need to, but try to keep all your points if you can. Getting started early can help you avoid this penalty.

Learning Outcomes

The syllabus lists a number of learning outcomes for this course. This assignment is intended to support several of theses:

Compilation: implement C programs using the C standard library, with separately-compiled modules; explain the steps of compilation; identify and fix errors that happen during compilation and execution.

Language: write, debug, and modify C programs using data types, control structures, operators, library utilities, and variables, including scope in a single function, across multiple functions, and across multiple modules.

Numbers: add and subtract unsigned and signed, two’s complement binary integers and convert among standard types including bases 2, 10, and 16; describe 16-bit and 32-bit IEEE floating representation and its consequences for rounding error, and convert between these formats and decimal.

Tools: utilize software development tools to implement, test, build, and trace C programs including, build automation, version control, static analysis, and dynamic analysis tools.