CS211 Homework 3

This homework is intended to verify your familiarity with stacks and give you more practice with C’s I/O functions. The assignment is to implement a Reverse Polish Notation (RPN) calculator. This is also known as postfix notation, as the operators follow their operands. As a programming assignment, this is a fairly standard one. The only complication beyond the norm lies in using C’s functions to handle inputs.

Calculations in RPN are simple:

1. Read in the next token (meaning a word or number surrounded by spaces)
2. If the token is a number, push it onto your stack
3. If the token is one of -, +, *, or /, then pop the top two values, perform the operation, and then push the result back onto the stack.
4. If there are more tokens, go back to 1. Otherwise, go to step 5.
5. Pop the last value on the stack. It is the result.

All numbers will be single digit values, so you can read them with fgetc (see lecture 7). Do not forget that numbers will be in ascii character values. There is also an ascii chart in lecture 7.

Some examples:

• For example, 2 + 3 would instead be represented as 23+.
• 23 + 4− would be parsed from left to right, first adding 2 and 3. That reduces the statement to 54−, and finally yields 1.

Operators always work on the top two operands on the stack.

• 123 + − will first add 2+3, leaving 1 and 5 on the stack. The then - will occur, and 1-5 will leave -4 on the stack.

Walking through one final example, step by step:

1. Input file is: 6 3 / 5 6 + *
2. ’6 ’is read and pushed onto the stack
3. ‘3’ is read and pushed onto the stack, which is now 6, 3
4. ‘/’ is read. 3 and 6 are popped from the stack, 6 / 3 is calculated and 2 is pushed back onto the stack.
5. ‘5’ is read and pushed onto the stack, which is now 2, 5.
6. ‘6’ is read and pushed onto the stack, which is now 2, 5, 6.
7. ‘+’ is read. 6 and 5 are popped from the stack, 5 + 6 is calculated and 11 is pushed back onto the stack.
8. ‘*’ is read. 11 and 2 are popped from the stack, 2 * 11 is calculated, and 22 is pushed onto the stack.
9. There are no more inputs, so the program pops 22 from the stack and returns it.

Parsing of equations in this notation is simplified and parenthesis are not necessary. For many years this was a preferred style for calculations.

Coding

A makefile and a test script are provided, along with a version of the stack from class that works on integers. You will provide a file named hw03.c. Your program should accept the name of a file. The file will have a single line that contains an equation in RPN notation. Your parsing code should ignore any tokens that are not operators or numbers.

Compile your code with make hw03. Test your code with make test. You can also manually test with the provided test .txt files.

Return Values

If no errors occur, your main function should return the result of the RPN calculations.

There are 4 possible errors to handle:

1. No input filename provided: return 244
2. Provided filename fails to open: return 243
3. The stack runs out of values at any time: return 242
4. The stack has excess values (more than 1) at the end: return 241

We will check for memory leaks with valgrind as well.

Testing

Download either the hw3_files.zip or hw3_files.tar (both have the same contents and are provided in case one format is unfamiliar).

When you extract the archive, you should see a makefile, a testing script named hw3_tests.sh, and several .txt files with test inputs.

Run make test to compile and test your program.

Submission

Submit your hw03.c file through Canvas.