Homework 9 - 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.

In this assignment you will implement a reverse polish notation calculator, also known as a postfix notation calculator. That article gives a brief overview of how to calculate the result using a stack data structure in the Explanation section.

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 / (integer divide) as well as integer literals. It must also use a stack data structure on the heap to keep track of calulations.

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.

Writing your code

For this and future assignments, we are hoping that you will still write your code in a command-line editor (vim, nano, etc) on the portal. If you need to refresh, please review Lab 1. However, starting with this homework, you are welcome to transition to working on VSCode.

Please note: using an online editor or compiler will still result in an immediate 0 on the assigment.

Using Visual Studio Code

One of the most popular GUI-based editors today is VSCode. It provides an interface that also allows you to connect remotely to a server, view and edit files on the server, and even allows opening a terminal to the server. However, as part of its remote connection, it runs a process on the server itself. Since that is not always practical, we delayed providing information about VSCode until this homework. If you’d like to use VSCode, please follow the instructions below.

Download Visual Studio Code from https://code.visualstudio.com/download. Once you have installed and opened Visual Studio, you should see a screen that looks like this:

Use VSCode to remotely work on the UVA CS portal nodes. To do this, on the activity panel (shown as panel A) in the diagram above, you should see an option called “Extensions” (about five buttons from the top). Search for and install the Remote-SSH plugin. You can install the extension by visiting the Visual Studio Marketplace https://marketplace.visualstudio.com/items?itemName=ms-vscode-remote.remote-ssh.

Connect VS Code to the CS department portal. In VS Code, select “Remote-SSH: Connect to Host…” from the Command Palette (F1, ⇧⌘P) and type ssh YourUserName@portal.cs.virginia.edu -A. When prompted, enter your password.

When connected, the sidebar (panel B) should display a file browser to your files on the portal. Additionally, you can access a termal connected to portal directly from VS Code. Click ont he terminal tab in panel D.

Examples

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

2 3

[ 2 ]
[ 3, 2 ]

4     - 5

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

+ * /

[ 4, 2 ]
[ 8 ]

Note that the program stopped when it encountered / on a stack with just one argument. Also note that the stack prints with the top of the stack on the left.

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
[ -1, 2 ]

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 [ 5, 7, 2 ]`	`$ echo -n "2 3 4 + 5" \| ./a.out [ 2 ] [ 3, 2 ] [ 4, 3, 2 ] [ 7, 2 ] [ 5, 7, 2 ]`

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 ]
[ 1, 2 ]
[ 0, 1, 2 ]
[ -1, 0, 1, 2 ]
[ -2, -1, 0, 1, 2 ]
[ 1, 0, 1, 2 ]
[ -1, 1, 2 ]
[ 2, 2 ]
[ 0 ]

Tips

When reading text, check the manual page for your read function (read, fgets, etc) to see how it reports an end-of-file EOF

You must create a linked-list based stack implementation. We will not supply any files to support this, though, so include your implementation in your rpn.c.

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; 
    }
    if (first) 
        puts("[ ");
    printf("%d", top->value);
    if (top->next)
        printf(", ");
    else
        printf(" ]");
    pstack(top->next, 0);
}

If you 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 submission site will open a few days before the deadline and will only allow a total of 15 submissions.

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 of an autograded component (for correctness) and a code style grade. The breakdown is as follows:

85% code correctness (passing Gradescope tests)
5% well indented (readable) code
- You should indent your code as if it were Python; that is, indent whenever you would use curly braces.
5% good variable names
- Use names that express your code’s meaning.
5% comments
- Document your code with comments so that you (and we) can better read what you wrote.
- Write comments that explain any tricky sections as well as tell us (in English) what each section of your code is intended to do.
- Hint: it might be helpful to write the comments first so that you have a rough sketch of your algorithm before implementation.

Submission

Submit your code to Gradescope.

Note: the Gradescope submission will not be available until a few days before the deadline, and will then only allow a total of 15 submissions. We encourage you to write your code early and test it before submitting to Gradescope.