PLACE |
spec |
solutions |
Standard ML |
There are three functions in this implementation. rpncalc
is the main one. It calls inputLine
to read in a line of input and then splits that line into non-blank pieces (calling tokens
with the function isSpace
as argument). Through the case
expression the resulting list of tokens tks
is checked on being non-empty; if it is, evalrpn
is invoked and its return value is printed. Finally, rpncalc
calls itself to repeat reading and evaluating. End of input causes inputLine
to return the value NONE
, in which case rpncalc
ends the execution of the program by calling OS.Process.exit
.
Normally, the return value of evalrpn
is the string representation of a number – the outcome of computing an RPN expression. If the computation fails, however, an error message results.
Through the function foldl
, evalrpn
scans the list of tokens, passing to foldl
the function evaltoken
, so that the latter is applied to each token and some accumulated value. That value is a list, used by evaltoken
as a stack for storing the intermediate results in the course of the computation. The initial value []
of the list is also passed to foldl
. The return value of foldl
is that same list, which then must contain only one number, otherwise the RPN expression is incorrect.
evaltoken
processes a token tk
by first checking if it represents a number. If so, that number is pushed onto the stack st
. Otherwise, if the token is a character for one of the arithmetic operations, the corresponding operation (one of op +
etc) is applied to the topmost two elements y
and x
of the stack, and the resulting number replaces them on the top of st
. When a token is neither a number nor an operation, an exception is raised.
All syntax errors in the input RPN expression are dealt with by throwing exceptions. At several points this is done explicitly, using the raise
operator. The exception Fail
is thrown which the language defines to be a general-purpose exception with no predefined meaning. Fail
requires an argument, so ""
is passed, but this value is actually immaterial as the handler does not use it. Other exceptions are thrown implicitly. They occur when the stack st
has no enough values stored for assigning to x
and y
, or when nth
is called to select an operation from the list of four but its second argument is a wrong index, due to tk
not being within "+-*/"
. Both explicit and implicit exceptions are handled at the same point – the expression that follows the keyword handle
.
In the program we make use of functions from several modules of the language's Basis library. We open
some of these modules so as the corresponding functions can be called with simple names. For the functions belonging to other modules, their names are prefixed by the module name and a dot.
One may notice that analyzing the token in evaltoken
seems complicated beyond expectation and difficult to follow. The library support for manipulating text data in Standard ML is rich and flexible enough to meet all practical needs, but not always straightforward in use: switching back and forth between string and substring types is too frequent, string searching does not return a position (despite the name of the function), etc.
open TextIO String Char Real fun evaltoken (tk,st) = case scan Substring.getc (Substring.full tk) of SOME (x,sr) => if Substring.string sr = "" then x::st else raise Fail "" | NONE => if size tk = 1 then let val (s,_) = Substring.position tk (Substring.full "+-*/") val y::x::r = st in List.nth ([op +, op -, op *, op /], size (Substring.string s)) (x,y) :: r end else raise Fail "" fun evalrpn s = (case foldl evaltoken [] s of [r] => toString r | _ => raise Fail "") handle _ => "error" fun rpncalc () = case inputLine stdIn of SOME s => (case tokens isSpace s of [] => () | tks => print (evalrpn tks ^ "\n")) before rpncalc () | NONE => OS.Process.exit OS.Process.success ; rpncalc ()
boykobbatgmaildotcom