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
value as the infix expression 2 + 3
. The infix expression 1/2 + 1/3
is
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 *
, and `` 3 * 5 - 2`` would be 3 5 * 2 -
.
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. For example, to evaluate 2 3 +
, you read in the tokens one
at a time, from left to right, and apply the following 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 the number 5 on the top.
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
the string "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: they should always return strings. See the
examples below for how the functions should behave.
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 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 when they 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 for handling 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.
Another idea for error handling 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 you should implement one of these ideas, or handle errors in some other systematic way that is at least as good as these approaches.
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 sume.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 producte.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 stacke.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 stacke.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 stacke.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 stacke.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-separated 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 theDouble
3.14.It will help with debugging if you create an instance of
Show
for theToken
type, e.g.:instance Show Token where show (Num n) = "<" ++ (show n) ++ ">" ...
If
t
isNum 5
, thenshow t
returns the string<5>
. The angle-brackets are added just to make it clear that this is a token and not a regular number.You should implement
show
equations for the rest of yourToken
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 design of your functions could reflect this.
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. Typeman dc
at the Linux command line for more information.