Homework 8 - Linked List & Postfix Calculator

From now on, we’ll assume that you work on homework by connecting to the CS portal and that you are familiar with the command line environment. If you have not been practicing with the terminal, we strongly encourage reviewing Lab 1.

We will also assume that you ran the setup script from that lab and have all modules (including clang and git) by default.

There are two parts to this homework assignment: LinkedList, and Postfix Calculator. These parts should be completed in the order that they are presented in this write up - linked list first, then postfix calculator second. Please make sure to read this write-up in its entirety so that you can best pace yourself for the assignment.

Part 1 - LinkedList

In part 1 of this homework, you will finish writing the implementation for a circular doubly-linked list in C. You will need to use malloc and free to store the list nodes on the heap.

Getting the part 1 starter code

In order to get our starter code for this homework, you’ll need to copy our starter code into your home directory. Use cd to enter your cso1-code directory, then issue the following command to copy our code.

cp /p/cso1/homework/linkedlist.* .

Now you have two files, a linkedlist.c file containing functions to implement and a linkedlist.h header file declaring the functions with documentation.

Writing your code

For this and future assignments, we are expecting that you will write your code using the portal. If you need to refresh, please review Lab 1. Feel free to use whatever editor you like (nano, vim, VSCode, etc.). If you are not yet comfortable with the terminal, you may find it helpful to use a command line editor.

Why a CLI editor?

It is common to interact with servers that do not have their own monitors. In these cases, you typically attach to the server via ssh and have access only to a terminal, not a full windowing environment. The more comfortable you are with doing common programming tasks in the terminal, the better these experiences will be.

Task

Edit the C file named linkedlist.c that contains implementations of functions for manipulating a circular doubly-linked list as described and declared in the header file linkedlist.h.

A doubly-linked list is a linked list where each node has a pointer to the previous and next nodes in the list (two pointers per node). In a normal doubly-linked list, the head node would have a NULL previous pointer (nothing’s before it), and the tail node would have a NULL next pointer (nothing’s after it). In a circular doubly-linked list, the head’s previous points to the tail and the tail’s next points to the head.

Your code in linkedlist.c should begin by including the given header file, #include "linkedlist.h". We will assume you use this exact linkedlist.h in our testing; if you change it, we will not use those changes in our compilation and testing of your code. Comments in linkedlist.h describe what each function is supposed to do.

For this part of the assignment, you will only need to write the implementations of the linked list insert and remove functions. All of the other functions of the linked list implementation have been fully and correctly implemented for you; they are included in the linkedlist.c file.

Testing your code

You should manually test your code, including using the lldb debugger and/or the debugging function provided below. Test all of the corner cases (NULL arguments; first-, last-, and middle-node arguments, finding values not in the list, etc). Do NOT rely on Gradescope to be your compiler and tester! The Gradescope submission site will open on Wednesday and will only allow a total of 15 submissions on each part of this homework.

Example testing code

We have also provided an example of some test code in the provided main function. Once everything is implemented correctly, this code:

int main(int argc, const char *argv[]) {
    cll_node *x = NULL;
    putchar('A'); cll_show(x);
    x = cll_insert(25, x, 1);
    putchar('B'); cll_show(x);
    x = cll_insert(1, x, 0);
    putchar('C'); cll_show(x);
    x = cll_insert(98, x, 1);
    putchar('D'); cll_show(x);
    x = cll_insert(0, x, 1);
    putchar('E'); cll_show(x);
    x = cll_insert(-8, cll_tail(x), 0);
    putchar('F'); cll_show(x);
    cll_node *y = cll_head(x);
    putchar('G'); cll_show(y);
    printf("Length: %lu (or %lu)\n", cll_length(y), cll_length(x));
    x = cll_remove(x);
    putchar('H'); cll_show(x);
    putchar('I'); cll_show(y);
    x = cll_remove(cll_find(y, 98));
    putchar('J'); cll_show(x);
    putchar('K'); cll_show(y);
    
    return 0;
}

should display:

A[]
B[*25*]
C[25, *1*]
D[25, *98*, 1]
E[25, *0*, 98, 1]
F[25, 0, 98, 1, *-8*]
G[*25*, 0, 98, 1, -8]
Length: 5 (or 5)
H[*25*, 0, 98, 1]
I[*25*, 0, 98, 1]
J[25, 0, *1*]
K[*25*, 0, 1]

Tips

1. I have yet to see a student implement their first correct circular linked-list without drawing box-and-arrow pictures.

2. Debugging can be easier if you can see all of the pointers involved. You may want to write your own cll_show function similar to the one above that also prints the addresses of each node and its pointers to prev and next.

3. Don’t use after free! We will test your code with the address sanitizer enabled and may also manually check for additional memory errors.

Part 2 - Postfix calculator

In part 2 of this assignment you will implement a reverse polish notation calculator, also known as a postfix notation calculator. That article also gives pseudocode for two algorithms; the left-to-right is probably a better match for line-by-line input, though you are welcome to read the full input and then run right-to-left algorithm (or any other correct algorithm you might design) if you’d prefer.

Your program (written in a file named rpn.c) should read stdin until either (a) it encounters an unknown token or (b) there is nothing left. It should split the input into tokens on whitespace (as defined by isspace in <ctype.h>), recognizing the four operators +, -, *, and % (modulo) as well as integer literals.

Your program should halt when it

• encounters an unrecognized literal
• reaches the end of the input
• is given an operator with insufficient operands to evaluate it

Before exiting for any of the above reasons, your program must print the remaining values on the stack. These must be presented on a single line, separated by commas within square brackets, with the top of the stack on the right. Optionally, your program may also print the contents of the stack every time it changes.

Examples

The following is one possible run of the program, with user-input highlighted and the optional print-stack feature included

2 3

[ 2 ]
[ 2, 3 ]

4     - 5

[ 2, 3, 4 ]
[ 2, -1 ]
[ 2, -1, 5 ]

+ * %

[ 2, 4 ]
[ 8 ]

Note that the program stopped when it encountered % on a stack with just one argument.

Note that in the above example, we run the code with ./a.out, then enter 2 3 and press enter, then 4 - 5 and press enter, then + * % and press CTRL-D to end input.

---

The following is one possible run of the program, with the optional print-stack feature not included

2
  3 -4 + not_a_number 5 4
[ 2, -1 ]

Note that the program stopped when it encountered not_a_number and did not continue running the 5 and 4.

---

You should also verify that if you end input early (by redirecting input, or by pressing Ctrl+D when running interactively) the program prints the final stack and exits:

Without intermediate stacks	With intermediate stacks
$ echo -n "2 3 4 + 5" | ./a.out [ 2, 7, 5 ]	$ echo -n "2 3 4 + 5" | ./a.out [ 2 ] [ 2, 3 ] [ 2, 3, 4 ] [ 2, 7 ] [ 2, 7, 5 ]

---

Make sure your code works with all numbers as input, including the 0 that most string-to-number converters give if they detect an error.

2 1 0 -1 -2 - - - -

[ 2 ]
[ 2, 1 ]
[ 2, 1, 0 ]
[ 2, 1, 0, -1 ]
[ 2, 1, 0, -1, -2 ]
[ 2, 1, 0, 1 ]
[ 2, 1, -1 ]
[ 2, 2 ]
[ 0 ]

Tips

Since you will be writing this program from scratch, we’ve provided some pieces of the implementation below to get you started.

You are welcome to make either a linked-list or array-based stack. We will not supply any files to support this, though, so include your implementation in your rpn.c.

The following will print an array-based stack:

char b4='[';
for(int i=0; i<size; i+=1) { 
    printf("%c %d", b4, stack[i]); 
    b4=','; 
}
puts(" ]");

The following will print a singly-linked-list stack (doubly-linked printing code was supplied with the previous HW):

void pstack(node *top, int first) {
    if (!top) { 
        if (first) 
            puts ("[ ]"); 
        return; 
    }
    pstack(top->next, 0);
    printf("%c %d", (top->next ? ',' : '['), top->value);
    if (first) 
        puts(" ]");
}

Below we provide two separate approaches to reading in and tokenizing input to get you started - the following will read in input character-by-character, breaking at an EOF (you will need to add a break for any other exit conditions):

char c;
while (1) {
    c = getchar();
    // Check for exit condition (EOF)
    if (c == EOF) {
        break;
    }
    // Check for newline character 
    if (c == '\n') {
        continue;
    }
}

While the following will read in input line-by-line into a buffer, breaking when EOF is met:

char buffer[4096];
while (1) {
    if (fgets(buffer, 4096, stdin) == NULL) {
        break;
    }
    // Remove newline from the end of the string
    buffer[strcspn(buffer, "\n")] = '\0';

    // Check for exit condition (EOF)
    if (feof(stdin)) {
        break;
    }
}

If you instead use strsep to split input into tokens, you’ll need to handle it retuning empty strings if two whitespaces appear in a row. Alternatively, making your own tokenizer is not difficult. Either way, you almost certainly want to test your tokenizer on its own before you try to merge it with your postfix evaluator.

Never compare strings with ==, as that compares addresses not contents. Use strcmp (or strncmp) instead.

Both atoi and strtol will work to convert strings into numbers, but strtol can also detect non-numbers because if it finds a non-number then it will leave *endptr == nptr. Note that although strtol says it “may” set errno to EINVAL if given a non-number, in practice most implementations do not do this so do not rely on it in your code.

Test your code

You should manually test your code, including using the lldb debugger, address sanitizier, and/or the debugging function provided below. Test all of the corner cases Do NOT rely on Gradescope to be your compiler and tester! The Gradescope autograder will only allow a total of 15 submissions for each part of this assignment.

Things we do not test

You do not need to correctly handle any of the following

• half-number tokens like 5more.
• fractions like 2.3.
• tokens without whitespace between them 2+3.
• bigger-than-int values like 123456789012345678901235901234567890
• no-input inputs like echo '' | ./a.out

Things we do test

• very very long lines
• many short lines
• lines where a multi-digit number will be split across a buffer-capacity boundary

Grading

For this assignment, the grade will consist only of an autograded component. The breakdown is as follows:

• 100% code correctness (passing Gradescope tests)
• Half of these tests will be testing part 1 (linkedlist.c) in the Homework 8 Part 1 Gradescope assignment
• Half will be testing part 2 (rpn.c) in the Homework 8 Part 2 Gradescope assignment

Our tests for part 2 will use our version of linkedlist.c (if you use a linked list implementation of a stack), so the correctness of your part 1 will not impact your part 2 score. If you would like to use our linkedlist.c implementation, make sure that you have an #include "linkedlist.c" line near the top of your file to link in our implementation.

Submission

Submit your rpn.c and linkedlist.c to Gradescope. Only submit linkedlist.c to the Part 1 assignment on Gradescope and only submit rpn.c to the Part 2 assignment. You may only submit a maximum of 15 times to each autograder, so you should test your code extensively by calling your functions in main(). After the 15th attempt on each autograder, Gradescope will accept submissions, but the autograder will not run; Gradescope will only report the score of the 15th attempt.