CS152 S16 HW 5

Due Wednesday, May 4th, 11:59pm

Goals for this homework

• Experience the beauty of reusing code and ADTs
• Use an ADT in a real-world setting
• Practice reading and write to files

You are expected to complete this assignment individually. If you need help, you are invited to come to office hours and/or ask questions on piazza. Clarification questions about the assignments may be asked publicly. Once you have specific bugs related to your code, make the posts private.

This homework has several problems. We are also providing you with some resources on printf and error handling for this assignment.

• Set up
• File Reading
• Problem 1: abstract data types
• Problem 2: auto_indent
• Problem 3: match_closures
• Submit

Set Up

Make a directory, hw5, for your work. Add that directory to your repository.

Then create empty files for all of the code files you are going to need to fill in. This makes it so that even if you're not done, the code will compile. Otherwise, the compiler will say that it can't find the files.

$ touch stack.h
$ touch stack.c
$ touch queue.h
$ touch queue.c
$ touch llist.h
$ touch llist.c
$ touch hw5.c
$ touch hw5.h
$ touch test_hw5.c

Now add those to your repository so that when you commit, it will commit them all.

$ svn add *

File Reading

You have already read in a file for which you knew the exact length. In this assignment, you are asked to read a file of unknown length. In order to help you out, here is code that reads in a file and then outputs every line to the screen.

#include <stdio.h >
#include <stdlib.h>

#define BUFSIZ 120

void display_file(char *filename)
{
  FILE *fp;
  char buf[BUFSIZ] = "Garbage";
  int i;
  
  if ((fp = fopen(filename, "r")) == NULL)
  {
    fprintf(stderr,"Could not open file %s\n",filename);
    return (1);
  }
  
  i = 0;
  while (fgets(buf, sizeof(buf), fp) != NULL)
  {
    printf ("Line %4d: %s", i, buf);
    i++;
  }
  
  fclose(fp);
}

Problem 1: abstract data types

You have already practiced implementing linked list functions for individual problems. Now you are going to implement some very generic linked list functions, then use them to implement two classic abstract data structures: stack and queue.

This exercise as a few purposes:

• Practice linked list implementation
• See how wonderful it is to reuse code rather than reinvent the wheel
• Use a single Makefile for multiple targets.
• See how abstract data types are set up to separate implementation from the interface. Object-oriented languages do even more of this, but we'll do what we can in C.

---

The first step is to implement some linked list functions in c. You will place the code in llist.c. I have already created llist.h and the associated skeleton llist.c file for you to use. Copy and paste it into a file called llist.h. You are expected to implement a linked list slightly differently than before. Notice that there is a separate linked list struct. What we were implementing before as a llist is now called a node. The llist has two pointers - a pointer to the first node (head) and a pointer to the last node (tail). You will implement a linked list that has both a head pointer and a tail pointer. See llist.h for full function headers to tell you what to implement.

Place your test code in test_hw5.c. I have provided a skeleton main file that does nothing. I have also provided a Makefile that contains compilation for llist only, stack (and llist), queue (and llist), and everything together. You may inspect the file to see how to use it. Once you inplement the some test cases, then type the following.

$ make hw5

To test it, type:

$ ./hw5

---

Don't forget to complete this portion, test it, and commit it before moving on!

---

The second step is to implement a stack, building on your linked list structure and operations. Whenever possible, call a function that was already implemented for your linked list. You should not perform any changes directly to the linked list.

Copy this stack.h file into your stack.h file. Then copy the skeleton stack.c code into your stack.c file. Fill in the proper code. Add test cases to test_hw4.c, and you are ready to test.

---

The third step is to implement a queue, again building on your linked list structure and operations. Whenever possible, call a function that was already implemented for your linked list. You should not perform any changes directly to the linked list.

Copy this queue.h file into your queue.h file. Then copy the skeleton queue.c code into your queue.c file. Fill in the proper code. Add test cases to test_hw4.c, and you are ready to test.

Problem 2: auto_indent

Write a function, auto_index, that properly indents a file. Place this in a file hw5.c. Place the function prototype into hw5.h. This function does two things:

1) It replaces all whitespace at the beginning of a line (whitespace consists of spaces or tabs) with the proper numbe of spaces, as defined by the input parameter. For example, if someone sets the space to 3, then each level of indentation will print 3 spaces.

2) It places all '{' and '}' on their own line at the indentation level of the code before the '{' and after the '}'.

Therefore, a file that looks like this:

int main(){int x; printf("Hi!\n");
int i;
for(i=0;i<10;i++){printf("%d\n",i);}
if (i > 10) 
print("The loop worked!\n");}

will become this:

int main()
{
   int x; printf("Hi!\n");
   int i;
   for(i=0;i<10;i++)
   {
      printf("%d\n",i);
   }
   if (i > 10)
   printf("The loop worked!\n");
}

Note the following simplifications from a full-working solution:
1. It does not go to a new line when it sees a semi-colon (1st printf)
2. It does not indent one-line basic-blocks that lack curly-braces (3rd printf)

---

The function signature is this:

void auto_indent(char *filename, int num_spaces);

Your code needs to open the filename for reading. In addition, it needs to create a new filename for writing. If the old filename was "file.txt", then the new file is "file_indent.txt". That is, it looks for the period and inserts "_indent" immediately before the period. If there is no period, then "_indent" is appended to the end of the filename.

You do *not* need to hand curly braces that are within quotation marks. This will not be a 100% fully functional program, but it will still be useful!

num_spaces is the number of spaces for each indentation level.

You may solve this in any order compared to check_closures.

---

To demonstrate that you have tested this code, create an input file named test_auto_indent.c. This input file has code in various states of disarray in terms of the indentation. Run it through your code (you can hard-code the filename into your main), and also submit the output (test_auto_indent_indent.c).

Problem 3: match_closures

You are to write a function that checks code for matching closures. That is, it looks for matching '[',']', '(',')', and '{','}'. It ignores everything else in the file, except that it keeps track of the line on which each character was stored.

Place this in a file hw5.c. Place the function prototype into hw5.h. The signature is:

void match_closures(char *filename);

If all of the characters line up, nothing is printed out. If, however, there is interleaving (see below), then an error is printed. The execution would look like this:

int main()
{
   int x;
   for(i=0;i<10;i++}
   {
      printf("%d\n",i);
   }
}

Note the '}' on line 3 that should be a ')'.

When it encounters the '}' on line 3 (we number starting at 0), then it prints out:

Unexpected } encountered on line 3.
Expected a match to ( on line 3.
Matches with { on line 1.

The first line of output is the character it was looking for (and line #).
The second line of output is the item that was expecting a match (and line #)
The third line of output is the line number of the most recent open character of the same kind that doesn't have a matching close.

If there is no open matching one waiting for a match, then do as follows below:

int main()
{
   int x;
   for(i=0;i<10;i++]
   {
      printf("%d\n",i);
   }
}

Note the ']' that should be a ')'.

When it encounters the ']' on line 3 (we number starting at 0), then it prints out:

Unexpected ] encountered on line 3.
Expected a match to ( on line 3.
No [ currently waiting for a match.

---

To demonstrate that you have tested this code, create a set of input files named test_check_closures_1.c, test_check_closures_2.c, etc. Each file has a different configuration that results in a mismatched closure, as well as a single file in which all closures are matching, but they are sufficiently complex to find. Don't forget to complete this portion, test it, and commit it before moving on!

Submit

At this point, you should have done the following:

• Created several files and filled in the proper information: stack.c, stack.h, queue.h, queue.c, llist.h, llist.c, hw5.c, test_hw5.c inside your hw5 directory. You should also have test files test_check_closures.c and test_auto_indent.c, with the associated test_auto_indent_index.c output file.

• $ svn add hw4.h hw4.c test_*.c
  

• Implemented all of your functions. If not, you at least need skeletons of your functions so that our automated tests will compile for the functions you did write.
• Compiled your executable manually and with the Makefile
• Implemented your test cases
• Executed your code
• Debugged your code

• $ svn commit -m "hw4 complete"