3/2/23, 7:50 PM Project 2: Reverse-Polish Notation
https://wsu.instructure.com/courses/1617964/assignments/8065307 1/4
Project 2: Reverse-Polish Notation
Due Friday by 11:59pm Points 100 Submitting a text entry box
Start Assignment
Overview
Reverse-polish notation is a way of writing expressions that avoids the need for parenthesis. It is also
known as postfix notation.
Instead of writing 2 + 2, we write 2 2 +. Why? Consider the following expression: 2 + ( 2 * 3 ). In this
expression, it’s important to do the 2 * 3 multiplication before the addition. However, if we use reversepolish notation, we can write it without parentheses like this: 2 2 3 * + . If we did use parentheses, it
would look like this: ( 2 ( 2 3 * ) + ), but they are not necessary. We know that ‘+’ and ‘*’ each take 2
arguments, so we can pair the operators to their operands without any ambiguity.
How is this expression evaluated? We don’t need to add parentheses manually. Instead, whenever we
see a number, we push it onto a stack. Whenever we see an operator, we pop enough arguments off the
stack, use them to compute the result, and push the result back onto the stack. Here’s an example of
what would happen after each step of “2 2 3 * +”. First, we break this string into an array of smaller
strings called tokens. Each token is separated from its adjacent tokens by whitespace. Then, for each
token, we perform an operation as follows:

Commands
Your calculator must support the following commands:

3/2/23, 7:50 PM Project 2: Reverse-Polish Notation
https://wsu.instructure.com/courses/1617964/assignments/8065307 2/4

Usage
Your calculator will be called by redirecting source code into standard input:
calc.exe < source_code.4th
(note: the source code extension is 4th because we are building an interpreter for the Forth
programming language without realizing it)
Output
After running the code, your calculator will print the stack out to standard output with the “print” function.
Be sure to reverse it so that the top of the stack is on the right. I.e., the program 3 2 1 should be printed
[3.0,2.0,1.0], with 1 being the top of the stack. If you do not reverse the stack, Haskell will print
[1.0,2.0,3.0] because the 1 is pushed last and is therefore at the top, and it prints from the top of lists to
the bottom.
First steps
Your first step will be to open the template I’ve given you for this project, template.hs. It contains some
already-built functions for you to put code into. I have also done the input/output for you (because it’s a
little weird in Haskell).
3/2/23, 7:50 PM Project 2: Reverse-Polish Notation
https://wsu.instructure.com/courses/1617964/assignments/8065307 3/4
Project 2 rubric
I suggest implementing comments first, because all of the code files contain comments. If you do not
successfully implement comment removal you won’t be eligible for most of the points in the project.
From there, the other 8 operations are all expected to be about equal in difficulty.
The result of tokenization is a list of strings. You will want to create a “runCode” function which takes the
top token, processes it, and then recursively executes on the next token. You can handle comments
here too if you wish. The “runCode” function should have type:
[String] -> [Float] -> [Float]
It will take a list of tokens and a stack and return a new stack. This function should be recursive (it
should call itself on the remainder of the tokens after it has processed the current one).
Tokenization is done with the built-in “words” function, which takes a string and returns a list of strings
(each of which is a function).
Rules
Be sure to follow these rules for the assignment. Breaking them will come with a discretionary grade
penalty, up to and including all the points.
This is an individual assignment. You must write the code yourself.
You must use Haskell for this project.
Submit your project as a single source file (it does not require splitting up into more)
No regexes
How to submit
Copy and paste your code file into the submission text box. Then, start writing a Canvas comment, and
attach your code file to the comment as a file. The code file must contain the same characters as the
submission.
Failure to submit correctly could result in a grade penalty.
Grading
You will be graded on whether each sample file returns the correct output. Ensure that you get the
correct output for each sample. There will be little or no partial credit awarded. If the program does not
output anything or if it crashes, it will likely receive a zero.
All sample files are provided, the same as in the BrainFriend assignment.
3/2/23, 7:50 PM Project 2: Reverse-Polish Notation
https://wsu.instructure.com/courses/1617964/assignments/8065307 4/4