Assignment 6: Watch where you point II

Due Friday, February 28, before midnight

The goals for this assignment are:

Work with pointer-based data structures
Strengthen C programming with strings and files

1. Update your repository

Do a fetch upstream to obtain the basecode for this assignment.

Using the command line

Open terminal and change your current directory to your assignment repository.
Run the command git fetch upstream
Run the command git merge upstream/main

Your repository should now contain a new folder named A06.

The fetch and merge commands update your repository with any changes from the original.

2. Matching braces

Implement a program, match_braces.c, that takes a C file as a command line argument and uses a stack to check for matched braces. If not all braces are matched, print the line where a mis-matched brace occurs.

$ make match_braces
gcc -g -Wall -Wvla -Werror match_braces.c -o match_braces
$ ./match_braces
usage: ./match_braces 
$ ./match_braces prog.c
Cannot open file: prog.c
$ ./match_braces prog1.c
Found matching braces: (21, 32) -> (23, 5)
Found matching braces: (25, 30) -> (28, 9)
Found matching braces: (17, 53) -> (29, 5)
Unmatched brace on Line 31 and Column 1
Found matching braces: (40, 47) -> (43, 5)
Found matching braces: (36, 18) -> (47, 1)
Unmatched brace on Line 34 and Column 34

Requirements/Hints:

Use your linked list implementation as a starting point.
Implement the functions push, pop, clear. Implementing print is also recommended to help you debug your assignment.
Use command line arguments to input the filename.
Print the usage if the user inputs an incorrect number of command line arguments
Print an error if your program cannot open the file
Use fgetc to read the file one character at a time. Update the current line number when you encounter \n. Update the current column as you read in each character.
To check for matched braces, push to the stack when you encounter a '{' and then pop from the stack when you encounter '}'. If the symbols pushed and popped do not match, there is an error.
The output of the program should match the line and column numbers that your editor (such as VS Code) reports when you check for matched braces.

Unlike last week, you need to open the files as text data. See File Input/Output for examples.

3. Tree

In the file, tree.c, implement a binary search tree. Do not change the header tree.h, nor the function declarations in tree.c. But you can add functions to tree.c! We recommend using the book "Data Structures and Algorithm Analysis in C" by Mark Allen Weiss. See the course webpage for a link.

$ make ./tree_tests
gcc -g -Wall -Wvla -Werror -Wno-unused-variable -Wno-unused-but-set-variable tree_tests.c tree.c -o tree_tests -lpthread
$ ./tree_tests
Running tests...
test 1: insert for empty tree: PASSED
test 2: name set correctly: PASSED
test 3: left is null: PASSED
test 4: right is null: PASSED
test 5: name set correctly: PASSED
test 6: right is null: PASSED
test 7: name set correctly: PASSED
test 8: item not in tree: PASSED
test 9: item in tree: PASSED
test 10: found correct object: PASSED
M
 l:A
 r:X
  l:P
A
M
P
X

Requirements:

You must not modify the basecode for tree.h or tree.c. You may add functions to tree.c
Your output should match the above and pass all tests

4. Dependencies

A dependency is a general software term for any software required by another. In this question, we will store files in a binary search tree so we can list their file dependencies, as determined by #include statements. For example, the file "Animal.h" depends on "Locomotion.h".

In the file, dependency.c, implement a program that builds a binary search tree of a given set of files. After building the tree, the program should give the user a prompt where they can list the processed files in alphabetical order and then query the dependencies of the file by giving the filename.

$ ./dependency  ` find code -name "*.h" -o -name "*.cpp" ` 
Processing 11 files
$ list
code/Animal.h
code/Bird.h
code/Duck.h
code/Fish.h
code/Fly.h
code/Locomotion.h
code/Seal.h
code/Swim.h
code/Walk.h
code/Whale.h
code/Zoo.cpp
$ code/Animal.cpp
code/Animal.cpp not found
$ code/Animal.h
code/Animal.h has the following dependencies
  string
  vector
  Locomotion.h
$ code/Zoo.cpp
code/Zoo.cpp has the following dependencies
  Animal.h
  Bird.h
  Duck.h
  Fish.h
  Seal.h
  Whale.h
  Locomotion.h
  Walk.h
  Fly.h
  Swim.h
$ apple
apple not found
$ quit

Requirements:

Check that a file is valid before adding it to the tree
Support the commands: quit, list, <filename>
Your program should take a list of files as command line arguments. The find command computes this list of files.
Use strstr and fgets to parse the source file and find lines containing #include
Strip the filenames from the #include lines when printing dependencies.

5. Submit your work

Push you work to github to submit your work.

$ cd {ASST}
$ git status
$ git add *.c
$ git status
$ git commit -m "assignment complete"
$ git status
$ git push
$ git status

6. Grading Rubric

Assignment rubrics

Grades are out of 4 points.

(2 points) matched braces
- (0.2 points) style and header comment
- (0.8 points) correct output and behavior, supports command line arguments
- (1.0 points) no memory errors
(1 points) Tree
- (0.1 points) style and header comment
- (0.4 points) implements all functions, passes all tests and does not modify basecode
- (0.5 points) no memory errors
(1 points) Dependencies
- (0.1 points) style and header comment
- (0.4 points) Correct behavior
- (0.5 points) no memory errors

Code rubrics

For full credit, your C programs must be feature-complete, robust (e.g. run without memory errors or crashing) and have good style.

Some credit lost for missing features or bugs, depending on severity of error
-5% for style errors. See the class coding style here.
-50% for memory errors
-100% for failure to checkin work to Github
-100% for failure to compile on linux using make