Assignment 4: Watch where you point

Due Friday, February 13th, 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 git pull to obtain the basecode for this assignment.

Your repository should now contain a new folder named A04.

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 a 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
Recommended algorithm: 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.
- Push to the stack when you encounter a '{'
- 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.

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! I recommend the book "Data Structures and Algorithm Analysis in C" by Mark Allen Weiss, which has classic C implementations of C data structures.

$ 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.

4.1. Implementing a console command program with a prompt

Your program should use readline and history to build your command loop. One possible implementation is below.

Read the man page to get documentation for readline, e.g. man readline

while (1) {
  // Get input from the user
  // if the user types "exit", break from the loop
  // else if the user types a command, execute it
}

Requirements:

Use the readline() function to get user input. This function supports backspace, tab completion, and more. Documentation for readline can be found here.
Use the add_history() function to save user history. This will allow arrow keys to work. Documentation for readline can be found here.
Your program should quit if the users types exit.

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