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
. Implementingprint
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
ortree.c
. You may add functions totree.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
andfgets
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