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 termainal Reverse-Polish-Notation program that uses the Deque.

Collaboration

For assignments in CS 2400, you will complete each of them on your own or solo. 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 instructor.

Setup

If you haven’t already, you need to follow the VMWare setup. We recommend you try and figure this out ASAP.

Once you have the VM setup, you should boot it up, and download the following tar file. To download them, you should open the terminal (which should be an application on the right hand side of the desktop) and use the provided command:

• wget https://www.seas.upenn.edu/~cis2400/22fa/projects/code/hw7.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 hw7.tar

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 poriton 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.c: 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.c: A short program to run the test_deuque.c tests.

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 useing 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 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:

Below are more details about how you should handle input:

• You can assume that every command line will contain no more than 100 characters.
• You should use the fgets 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, 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:

• en.cppreference.com/w/c
• The linux man pages

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, fgets
• <ctype.h> tolower, toupper
• <string.h> strstr, strcmp
• <stdlib.h> malloc, free, exit, EXIT_SUCCESS, EXIT_FAILURE

The list is only suggestive 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 and Testing

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.

When you run test_suite it should look like the following if you passed all tests:

Deque Basic Test...             Passed
Deque PushPop Front Test...     Passed
Deque PushPop Back Test...      Passed
Deque Iterator Basic Test...    Passed

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. Valgrind will be gone over in lecture on monday 11/07 but you should be able to figure out most of what you need for this assignment on your own if you want.

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