| |
Define a datatype ''a bst that will allow you to build a binary
search tree out of any equality type for which you can also provide an ordering
function. (Note: You may find it helpful to get some practice with datatypes
by first defining a datatype for
integer binary search trees, which need not carry around an ordering function.)
Define the following functions that operate on this type:
newTree : ('a * 'a -> bool) -> 'a bst
Takes an ordering function for a given type and returns a base (empty) tree
which you can then use to build trees of elements of that type.
isEmpty : 'a bst -> bool
Reports whether the given tree is empty.
inTree : ''a -> ''a bst -> bool
Reports whether the given element is in the tree somewhere.
insert : ''a -> ''a bst -> ''a bst
Returns the tree that results from inserting the given item into the given
tree. If the element is already in the tree, DO NOT insert another copy.
delete : ''a -> ''a bst -> ''a bst
Returns the tree that results from removing the given item from the given
tree. If the item is not in the tree, the function just returns the tree
unmodified.
This is the hardest function in this problem. Do not traverse the tree
to create a list, delete the element, and rebuild the tree. This is way
too expensive and will also generally create a degenerate tree when it is
done (why?). If you don't know how to delete an element from a binary search
tree, go find an elementary data structures text. (Note, you do not have
to worry about keeping the tree balanced, just don't do the dumb thing that
builds a totally degenerate tree).
inorder : 'a bst -> 'a list
Returns a list of the items in the tree in the order of the in-order traversal
of the tree.
list_to_tree : (''a * ''a -> bool) -> ''a list -> ''a
bst
Returns a tree that has all the elements of the list, inserted in the order
in which they occur in the list. Because this needs to build a new tree,
it needs to be given the ordering function to be used for the tree's construction.
Part II: A User Defined Abstract Type for Polymorphic Stacks:
|
| |
Define a structure that implements the following signature:
signature STACK =
sig
type 'a stack
exception StackUnderflow
val emptystack : 'a stack
val empty : 'a stack -> bool
val push : 'a -> 'a stack -> 'a stack
val top : 'a stack -> 'a
val pop : 'a stack -> 'a stack
val poptop : 'a stack -> ('a * 'a stack)
end
used to store a stack of values of
type 'a. You should construct it from first principles. In
particular, do not use the built-in ML list type as the core of the construction.
The meaning and behavior of each object defined is as follows:
emptystack : 'a stack
Actually just a val, not a function, it is set equal to the
(hidden) constructor you use to represent the empty stack, since the name
of that constructor is not available to the user.
empty : 'a stack -> bool
Returns true if the given stack is empty, and false
otherwise.
push : 'a -> 'a stack -> 'a stack
Returns the stack that results from pushing the given item onto the top
of the given stack.
top : 'a stack -> 'a
Returns the element currently on the top of the given stack. If the stack
is empty, raises the exception StackUnderflow.
pop : 'a stack -> 'a stack
Returns the stack that results from removing the element currently on the
top of the given stack. If the given stack is empty, raises the exception
StackUnderflow.
poptop : 'a stack -> ('a * 'a stack)
Returns the element currently on the top of the given stack, paired with
the stack that results from its removal. If the given stack is empty, raises
the exception StackUnderflow.
You should include the code for the signature before the code for your structure.
Define your structure so that it is constrained to match the signature.
Do not define it so that the the structure is hidden from the user (i.e abstracted
from view).
Part III: A Simple Postfix Calculator:
|
| |
In this problem you will prepare for the first phase of the interpreter
project by constructing a simple read-eval-print loop based desk calculator.
The goal is to provide a very stripped down version of the unix program dc.
The program will use a stack (defined and implemented above) to store real
values. The program starts up, prints a welcome message, and then waits
for input. Each line of input should contain only a single token, either
a real number (syntactically specified in the last project), or a command.
If the input is a number, then that value is pushed onto the stack. If the input is a command, then
the appropriate action is performed. The commands and their corresponding
actions are:
q
Exit the program.
p
Print the value on the top of the stack (without changing the stack). If
the stack is empty (i.e. attempting to read the top value causes a StackUnderflow
exception to be raised) then handle the exception by printing the message
"Stack Underflow" for the user.
+
Pop two numbers off the stack, add them, and push the sum on the stack.
*
Pop two numbers off the stack, multiply them, and push the product on the
stack.
-
Pop two numbers off the stack, subtract the second from the first, and push
the difference on the stack.
/
Pop two numbers off the stack, divide the first by the second, and push
the difference on the stack.
If any of the last four actions is attempted when there are fewer than two
numbers on the stack, then handle the resulting StackUnderflow
exception by printing the "Stack
Underflow" message for the user. The stack should be left in
the state it was in before the attempt to execute the command was made.
Any syntax error should cause the message "Bad Input" to be printed. The
easiest way to handle the syntax checking is to first check the input line
against each of the commands, and then if it doesn' t match
any of them, just assume it is a real number and try to convert it. If it
is not a real, you'll get an exception from string_to_real.
Here is a sample run of the program. If you are unsure of proper behaviors,
you can try an executable copy of the sample solution by running /cs/cs131/bin/sml-cs131-proj3soln
on turing:
> /cs/cs131/bin/sml-cs131-proj3soln
Welcome to the desk calculator sample solution!
p
Stack Underflow
3
-2
-4
p
~4.0
+
p
~6.0
/
p
~2.0
p
~2.0
/
Stack Underflow
p
~2.0
5
/
p
~2.5
3 *
Bad Input
.
Bad Input
3.
Bad Input
-3
*
p
7.5
q
So Long!
|
You will need a copy of string_to_real from your solution
to the last assignment (or the sample solution). You will also need the
following function to get input from the user (it gets a line of input from
standard in, and strips off the trailing \n.):
fun getInput () =
let
val inputline = TextIO.inputLine TextIO.stdIn;
in
if inputline <> ""
then String.substring(inputline,0,(size inputline) - 1)
else inputline
end;
The core of your solution should be a function named loop, which takes
a real stack as a parameter. Initially this stack will be empty.
Each call to the function gets and processes one line of input as appropriate,
and then calls the function recursively with the new stack state. The only
other function to be defined is dc, which takes unit as a parameter,
prints a welcome message, and then makes the initial call to loop.
When the user enters the quit command, and loop returns, then
dc should print a parting message before returning.
You may define as many auxilliary support functions as you see fit.
Your solution to the problem (which should not include the code for a stack) should be in
the form of a functor named Make_DC which, given a structure of signature
STACK as defined in the last problem, produces a structure of signature
DC, which signature has the definition:
signature DC =
sig
val dc : unit -> unit
end
Include the definition of the signature DC before the code for your functor.
After the code for your functor, include a command to build a structure
of signature DC named dc (by applying the functor to the
structure from the last problem).
|
