CIS 2400 (Fall 2024) Home Schedule Assignments Tools & Refs HW 03: Deque and Reverse Polish Notation Calculator

This assignment gives students hands on experience with C, specifically memory allocation, structs and I/O.

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

This assignment is also sort of split into two parts.

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.

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:

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:

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:

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.

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

Testing

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]

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