Introduction

In this assignment, you will write a C program that will emulate the action of a classic stack based calculator.

This assignment will allow you to exercise a few aspects of the C language including

getting input from stdin
using the sscanf function to parse string content
handling dynamic memory with malloc and free
printing formatted output using printf

This assignment is also sort of split into two parts.

Implementing a Deque & Deque Iterator
Implementing a terminal Reverse-Polish-Notation program that uses the Deque.

Collaboration

For assignments in CIS 2400, you will complete each of them on your own. However, you may discuss high-level ideas with other students, but any viewing, sharing, copying, or dictating of code is forbidden. If you are worried about whether something violates academic integrity, please post on Ed or contact the instructors.

Setup

You will need the same docker environment that we set up for previous assignments.

Once you have the environment set up, you should boot it up, and download the tar file here:

curl -o rpn.tar https://www.seas.upenn.edu/~cis2400/current/projects/code/rpn.tar

After downloading the tar file, you should be able to type in the command “ls” in the terminal, or use the file explorer to see the download tar file. Once you confirm that the file is downloaded, run the following command to decompress the files:

tar -xvf rpn.tar

You should now have a directory called rpn that contains the starter files for this assignment.

Instructions

All of the code you will submit for this assignment should be contained in Deque.c and rpn.c. This means that your code should work with the other files as they are when initially supplied. Note that you can modify the other files if you like, but we will be testing your code against un-modified versions of the other files.

Part 1: Implement a Deque

If you’ve programmed in higher level programming languages like Java, Python, or others, then you probably made use of a large standard library, filled with data structure implementations ready for you to use. In C, we have to make data structures ourselves or use an external library. In this part of the assignment, we will be implementing a fairly common data structure called a Double-Ended Queue or Deque. A Deque is a data structure that acts similarly to a list, where we have a sequence of values, but we can only add or remove elements from the front or end of the list. As a result, we will be implementing the data structure with a doubly-linked-list. A doubly linked list is a linked list where each node has both a next pointer and a prev pointer to access both the node before it and after it in the list.

As we create the Deque we need to specify which data type we are storing, which will be structs of type rat_num which is defined in rat_num.h. rat_num represents a rational number which we will need to use for implemting our cacluator. No math should be done with rat_num structs in this portion of the assignment, this portion is simply creating a structure to store rat_num structs.

In addition to creating a Deque, we will also be creating an iterator for the Deque so that users can access elements that aren’t the front or back of the Deque. As a result, there are three struct types that we will be using in this assignment.

Deque: The structure containing data to maintain the Deque, such as the current number of elements, a pointer to the first node, and a pointer to the last node.
DequeNode: The node structure that we will use for our doubly linked list internals. This has a payload field of type rat_num, and pointers to the next and prev elements in the list.
DQIterator: The structure that represents our iterator. This contains some meta-data necessary for the iterator such as the node it is currently on and a pointer to the overall Deque. Note that it is necessary to have a pointer to the overall Deque since the iterator can remove elements, which may affect the information stored in the Deque structure.

There are also further notes about these structures and the structure of the code in Deque.h. We recommend that you read through this file before you start your implementation.

You will find the deque starter code in the tar file mentioned in the setup section above. Among these files, a few stand out:

Deque.h: Contains the declarations and extensive comments detailing the functions you will have to implement for this assignment. Also contains information about the internal structures used for the Deque and its iterator.
Deque.c: Where you will be writing all of your code for the assignment. You will have to implement all of the functions specified in Deque.h.
test_deque.cpp: A short test file containing the tests we will run on the deque. You do not have to read this file, but you can add print statements to it if it would help with debugging.
test_suite.cpp: A short program to run the test_deuque.cpp tests.
catch.cpp and catch.hpp: the testing library called “Catch2” that we are using in this class.

Once you have finished implementing Deque.c, we highly recommend you test it before moving on to the next part. Take a look at the Compiling and Testing section below for more.

Part2: RPN

For those of you that are not familiar with stack based calculators or Reverse Polish Notation, I would suggest the following Wikipedia site:

http://en.wikipedia.org/wiki/Reverse_Polish_notation

In such a calculator, all operations are organized around a list-like datastructure called a Stack. Note that when we refer to a Stack in these instructions, we are not referring to the stack in memory layout that maintains stack frames and local variables. To avoid this confusion, we will talk about using a Deque, which can also do all of the operations a Stack data structure can do. Entering a number like 37 would push that value on to the back end of the Deque, entering an operation like + would consume numbers from the back of the deque and push the result onto the back of the deque. Your C code must read the entries that the user types on the standard input, manage the deque and print the correct outputs when needed.

We have provided a mostly empty file rpn.c where you will write your code. We highly suggest you look at the main_queue.c code that was shown in lecture as it may help you handle reading user input, and printing out to the user.

The program that you implement should run a loop which continually reads the commands that the user types on stdin and performs the requisite operation as follows:

Input	Action
A decimal integer	Add the number to the back of the deque. Your inputs are all decimal integers so if you type 5 <return> the rational number 5/1 should be added to the back of the deque.
+	Pop the last two entries off of the deque and place the sum at the pack of the deque.
-	Pop the last two entries off the deque subtract the last entry from the second to last and place the result at the back of the deque. Egs 5 <return> 4 <return> – <return> would result in (5-4)=1 at the back of the deque
*	Pop the last two entries off of the deque and place their product at the pack of the deque.
/	Pop the last two entries off the deque divide the second to last entry by the last entry and place the result at the back of the deque. Egs 5 <return> 4 <return> / <return> would result in (5/4) at the back of the deque. If the division results in a division by zero you should print out the string "DIVIDE BY ZERO" and terminate the program cleanly freeing all memory that you have allocated.
dup	Duplicate the value at the back of the deque so after this command the two values at the back of the deque should be the same.
swap	Swap the order of the two entries closest to the back in the deque.
quit	Exit the program freeing all memory that you have allocated.
drop	Delete the entry at the back of the deque
clear	delete all entries in the deque

Below are more details about how you should handle input:

You should use the getline command to safely read the command line that the user typed.
For the commands that are typed, it should not matter whether the characters are upper case or lower case or a mixture of both, your program should perform the required operation, so if the user types dup, DUP or dUp, the same thing should happen.
If there are not a sufficient number of entries in the deque to perform the requested operation, your program should print out “STACK ERROR” and terminate the program, cleanly freeing all memory that you have allocated.
At the end of every numeric entry or command that does not produce an error, and is not the quit command: your code must print the value currently at the back of the deque followed by a newline (ie ‘\n’). The numeric value should be in the form numerator/denominator egs. 19/6. Note that these values should be printed in their simplest form. We provide the function gcd in rpn.c to find the greatest common denominator between two numbers which should help you with this. You can either store the values in their simplest form or do the conversion when you print them.

Standard C libraries

In order to program effectively in C, you will want to begin to familiarize yourself with the Standard C Libraries. You can find a useful reference to them many places online, though ones that we have liked include:

These utilities are packaged into collections of functions that you can call from your code. In order to avail yourself of these routines, you should #include the relevant header files at the beginning of your program like so:

#include <stdio.h>
#include <ctype.h>

Here are some standard C library routines that you may want to look at:

<stdio.h> printf, sscanf, getline
<ctype.h> tolower, toupper
<string.h> strstr, strcmp
<stdlib.h> malloc, free, exit, EXIT_SUCCESS, EXIT_FAILURE

The list is only suggestive and not comprehensive - you don’t have to use any of them if you don’t want, feel free to use other functions that you find in the standard libraries if you prefer them.

Compiling

We have supplied you with a Makefile that can be used for compiling your code into an executable. To do this, open the terminal, navigate to where your code files are and then type in make.

You may need to resolve any compiler warnings and compiler errors that show up. Once all compiler errors have been resolved, if you ls in the terminal, you should be able to see an executable called test_suite and another called rpn. You can then run each by typing in ./test_suite and ./rpn respectively.

test_suite will test your deque implementation to make sure it works. You should make sure this works before you move on to implement rpn
rpn is the program you write in part 2 that you can test manually.

Note that your submission will be partially evaluated on the number of compiler warnings. You should eliminate ALL compiler warnings in your code.

Testing

Other than the autograder, you will have to test rpn.c by hand. We provide how to test your Deque implementation here:

After compiling your solution with make, You can run all of the tests for the Deque by invoking:

./test_suite

You can also run only specific tests by passing command line arguments into test_suite

For example, to only run the DQIterator tests, you can type in:

./test_suite [Test_DQIterator]

Note: you may have to type ine ./test_suite \[Test_DQIterator\] for it to work.

You can specify which tests are run for any of the tests in the assignment. You just need to know the names of the tests, and you can do this by running:

./test_suite --list-tests

These settings can be helpful for debugging specific parts of the assignment, especially since test_suite can be run with these settings through valgrind and gdb!

Valgrind

We will also test your submission on whether there are any memory errors or memory leaks. We will be using valgrind to do this. To run it yourself, you should try running: valgrind --leak-check=full ./test_suite for test_suite and valgrind --leak-check=full ./rpn for rpn.

If everything is correct, you should see the following towards the bottom of the output:

==1620== All heap blocks were freed -- no leaks are possible
==1620==
==1620== For counts of detected and suppressed errors, rerun with: -v
==1620== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

If you do not see something similar to the above in your output, valgrind will have printed out details about where the errors and memory leaks occurred.

Submission

Please submit your completed Deque.c and rpn.c files to Gradescope