Assignment 4: A Postfix Calculator in Haskell

In this assignment, your task is to create a postfix calculator, that implements all of the operations described below. In a postfix calculator, expressions are written using postfix notation, i.e. the operator comes after the operands.

For example, the postfix expression 2 3 + evaluates to 5, i.e. the same thing as 2 + 3. The infix expression 1/2 + 1/3 would be written 1 2 / 1 3 / + in postfix.

Postfix expressions don’t use brackets, and don’t use any operator precedence rules. For example, the infix expression 3 * (5 - 2) would be written 5 2 - 3 * in postfix.

For this assignment, we define tokens as follows:

  • Numbers. These are Haskell Double values.
  • Operators. An operator is a function that does something to the stack. All the operators are defined below. The name of an operator is a string consisting of 1, or more, characters, that doesn’t start with a number, and contains no spaces.

To evaluate a postfix expression, you need a stream of tokens and a stack that holds tokens. To evaluate an expression like 2 3 +, you read in the tokens one at a time, from left to right, and apply these rules until there are no more tokens:

  • If the token is a number, push it onto the stack.
  • If the token is an operator, then apply it to the stack. This usually involves popping one or more items from the stack, and pushing the result onto the stack.

So, starting with an empty stack, to evaluate 2 3 +, first 2 is pushed onto the stack, and then 3 is pushed onto the stack. The third token, +, pops the top two elements of the stack and then pushes their sum. So now the stack contains just the number 5.

Required Code

Postfix expressions consist of tokens, and so you must have a data type called Token defined in your program like this:

data Token = Num Double | ...

A number is a token, and Num Double must be part of your Token data type as shown. After that, you should add a constructor for each other kind of token. The exact details of this are up to you, and a good choice here can make the rest of your program much simpler.

You must also include a function called calcStack with the following signature:

calcStack :: String -> String

The input to calcStack is a string of space-separated tokens, and the output is the entire stack, as a string, after all the tokens from the input string have been processed.

You must also include a function called calc, that is similar to calcStack, except it returns just the top element of the stack (as a string). It must have this signature:

calc :: String -> String

If the resulting stack is empty (and so has no top element), it should return a message such as “empty stack”.

Don’t change the signatures of these required functions! Otherwise, the marking software will probably give you 0.

Both calc and calcStack are meant to be user-level functions that return neatly formatted and readable strings in all cases. Neither of them should ever cause an error.

You can write any other helper functions you need. Aim to write beautiful source code that is clear, simple, short, reasonably efficient, and highly readable. Stick to functions in the standard Haskell prelude, and to code you wrote yourself. Do not import any Haskell modules (except for QuickCheck — you can use that for testing if you like), and do not use any code that you didn’t write yourself. Don’t copy answers/code from the web or other people!

Please include type signatures for all top-level functions, and use comments to make your program more readable.

Error Handling

Error handling is an important part of any calculator: the user could enter invalidly formatted expressions, or errors like division by 0 could occur almost anywhere. As mentioned above, the calc and calcStack operations can never cause an error. So you should think about a strategy for handling errors.

Here are two suggestions about how you might want to handle errors. First, Maybe can be used as the type for some inputs or outputs for functions. For instance, you might use Maybe to implement a function that returns the top element of a stack like this:

topStack :: [a] -> Maybe a

The stack is assumed to be implemented as a list, and the result is either the head of the list (i.e. the top element of the stack), or Nothing, which means there stack was empty and has no top element.

The second idea for error handling you might want to consider is to add a special error value to the Token type called Err String. When an error occurs this special token value can be returned with an appropriate error message.

You don’t need to implement these ideas, but we do want to see you handle errors in some thoughtful and general way.

Postfix Operators

The following operators are unary:

  • inc

    e.g. “3 inc” evaluates to “4”, “3 inc inc” evaluates to “5”

    When the expression “3 inc” is evaluated, first 3 is pushed onto the stack. Then inc pops the top of the stack (which is the 3 that was just pushed), adds 1 to it, and pushes the result. So the stack ends up with 4 on the top.

    The operators below all work in the same way: they get their inputs from the stack, and push their result when they’re done.

  • dec

    e.g. “3 dec” evaluates to “2”, “3 dec dec” evaluates to “1”

  • sqrt

    e.g. “3 sqrt” evaluates to “1.7320508075688772”

  • sin

    e.g. “3 sin” evaluates to “0.1411200080598672”

  • cos

    e.g. “3 cos” evaluates to “-0.9899924966004454”

  • inv

    e.g. “3 inv” evaluates to “0.3333333333333333”, “0 inv” evaluates to “Infinity”

The following operators are binary:

  • +: pops the top two elements of the stack and pushes their sum

    e.g. “4 2 +” evaluates to “6”

    To evaluate “4 2 +”, first 4 is pushed onto the stack, and then 2 is pushed. The + pops the top 2 elements of the stack, adds them together, and pushes the result. So 6 ends up on top of the stack.

    Calling + on a stack with fewer than 2 elements is an error.

  • *: pops the top two elements of the stack and pushes their product

    e.g. 4 2 * evaluates to “8”

    Calling * on a stack with fewer than 2 elements is an error.

  • -: pops the top two elements of the stack and pushes their difference (make sure to get the order right!)

    e.g. “4 2 -” evaluates to “2”, “2 4 -” evaluates to “-2”

    Calling - on a stack with fewer than 2 elements is an error.

  • /: pops the top two elements of the stack and pushes their quotient (make sure to get the order right!)

    e.g. “4 2 /” evaluates to “2”, “2 4 /” evaluates to “0.5”, “2 0 /” evaluates to “Infinity”, “0 0 /” evaluates to “NaN”

    For division by 0, the returned values are whatever the Haskell / operator returns.

    Calling / on a stack with fewer than 2 elements is an error.

  • +all: adds all the numbers on the top of the stack (stopping at the end of the stack, or the first non-number token)

    e.g. 1 2 3 4 +all evaluates to “10”, 4 +all evaluates to “4”

    Calling +all on an empty stack is an error.

  • *all: multiplies all the numbers on the top of the stack (stopping at the end of the stack, or the first non-number token)

    e.g. 1 2 3 4 *all evaluates to “24”, 4 *all evaluates to “4”

    Calling *all on an empty stack is an error.

The following operators manipulate the contents of the stack:

  • dup: pushes a copy of the top element of the stack

    e.g. after 4 dup, “4 4” is on top of the stack; 4 dup * evaluates to “16”

    Calling dup on an empty stack is an error.

  • pop: removes the top element of the stack

    e.g. after “4 5 pop”, the top of the stack is “4”

    Calling pop on an empty stack is an error.

  • clear: removes all elements from the stack

    e.g. after “1 2 3 clear”, the stack is empty

    Calling clear on an empty stack returns the empty stack.

  • swap: changes the order of the top two elements of the stack

    e.g. after “4 1 swap”, the top 2 elements of the stack are “1 4”; “4 1 swap -” evaluates to ” -3”

    Calling swap on a stack with fewer than 2 elements is an error.

Examples

Here are some examples of calling calc.

> calc "1 2 + 3 *"
"9.0"

> calc "1 2 3 * +"
"7.0"

> calc "2 sqrt 3 sqrt +"
"3.1462643699419726"

> calc "11 dup *"
"121.0"

> calc "0 5 /"
"0.0"

> calc "5 0 /"
"Infinity"

> calc "2 3 + 4 2 +all"
"11.0"

> calc "2 3 + 4 2 *all"
"40.0"

> calc "2 3 + 4 2 clear"
"empty stack"

> calc "2 3 inc * pop"
"empty stack"

> calc "3.2 sin dup * 3.2 cos dup * +"
"1.0"

> calc "2 +"
"+: not enough args"

> calc "dec"
"dec: empty stack"

Your error messages don’t need to be exactly as shown here. As long as they are clear and easy to read, other error message formats are okay.

The output for calcStack will be the entire stack of tokens, and what that looks like will depend upon your show implementation for Token; be sure to clearly indicate the top of the stack.

What to Submit

When it is time to submit your work, please put all your code into a single file named a4.hs and submit it on Canvas.

Hints

  • The standard Haskell function words converts a string of space-string words into a list of strings, e.g.:

    > words "  2     3 inc *   pop "
["2","3","inc","*","pop"]

  • The expression read "3.14" :: Double will convert the string "3.14" to the Double 3.14.

  • It will help with debugging if you create an instance of Show for the Token type, e.g.:

    instance Show Token where
  show (Num n)  = "<" ++ (show n) ++ ">"
  ...

    If t is Num 5, then show t returns the string <5>. Then angle-brackets are added just to make it clear that this is a token and not a regular number. You can certainly show a number in a different format that you think is more readable.

    You should implement show equations for the rest of your Token type as well.

  • A useful way to think about the functions for a postfix calculator is that they take a stack as input, and return a modified stack as output.

  • The Linux command dc is a postfix calculator you can use to check your results. For example:

    $ dc
2 3 + 5 * p
25

    p prints the top element of the stack, i.e. the result of the most recent calculation. Type man dc at the Linux command line for more information.