PLACE |
spec |
solutions |
Erlang |
A program in Erlang is a set of functions, and a function can only be in a module, so a program consists of at least one module. Correspondingly, the following program starts with defining a module rpn
, together with a list (of a single item, main
) of its publicly available functions and lists of functions imported from standard library modules.
In these lists, each function's name is accompanied by an integer, specifying the number of arguments the function takes. There may be functions with the same name but with different numbers of parameters in a module, which is the way to overload function names in Erlang: since it is a dynamically typed language, parameters have no types assigned to them, and there is no way to discriminate between the homonymes other than by their number of parameters. The program does import and use two such functions, substr/2
and substr/3
.
Importing from io
, string
and regexp
makes it possible to refer to the listed library functions without prefixing their names by the names of the modules to which they belong. Two other functions, stop
and foldl
, are used in the program without import declarations, and accordingly they are prefixed. Yet other functions, such as e.g. length
and hd
, are imported by default or considered built-in, so need not be prefixed.
Since main
is the only exported function, it is it that ‘impersonates’ the program: it reads an input line and passes it to evalrpn
after splitting it into a list of tokens. (get_line
keeps the end-of-line character in the string which it returns, so splitting includes that character together with the space and tab characters.) Upon encountering end of input, get_line
returns the eof
atom, so that matching the result against eof
leads to calling stop
which terminates the program. Until that happens, main
tail-calls itself to repeat reading time and again.
On an empty token list, evalrpn
does nothing but formally returning the (not used anyway) ok
value. A non-empty list Tks
is passed to the foldl
function whose task is to traverse the list, processing each token as needed in order to evaluate the RPN expression. foldl
is a higher-order function of the kind typically used to express iteration on lists in functional languages. For the actual token processing it calls the anonymous function which it receives as its first argument. That function does a step of the computation by transforming a token Tk
and a list Tks
into a new list (to be the new value of Tks
), thus maintaining a stack of intermediate values within Tks
.
If Tk
happens to be an operator – one of +
, -
, *
, and /
– two numbers, Y
and X
, are popped off Stk
and the operation is performed on them (for which the string Tk
has to be converted to an atom and then prefixed by the name of the erlang
module, also an atom). The result is pushed on the new stack, Z
. Otherwise Tk
is considered to represent a number, and to_number
is called to obtain its value. Again, the value is then pushed on the stack.
As the call of foldl
is nested in a try-of-catch
expression, possible syntactic errors in the RPN expression result in exceptions caught in the catch
part. When foldl
returns normally, its result – the stack – is matched against the pattern [X]
to see if there is only one item left in it. Failing the match, the error
atom is produced instead of X
. If, instead of returning, an exception is raised from within foldl
, the catch
makes sure that, as above, the error
atom is produced as the result of try-of-catch
. Whatever the outcome, it gets printed by write
, and the output line is terminated by nl
.
An exception can be raised implicitly or explicitly. The first occurs when there are not sufficiently many values in Stk
to assign to Y
and X
. Explicit exception is raised by calling throw
within to_number
to signal that the token being considered does not represent a number. The two kinds of exceptions have different exception types so that the program could differentiate between them if necessary, using different exception patterns in catch
, but in our case this is not done: the _:_
pattern is an all-matching one, effectively ignoring the distinction not only between exception types but also between the values carried along by the actual expressions as they occur.
Erlang has different functions to check whether a string represents an integer or a real number, respectively, and to return that number in case of success. As we want to handle both kinds of numbers, we do make use of both kinds of functions. However, by the language's definition, the representation of a real number cannot have a leading or a trailing decimal dot. Therefore, such representations have to be modified to make them acceptable to Erlang's string-to-number transforming functions. To discriminate between the several number representations, to_number
performs several matching operations using regular expressions. A possible trailing dot is removed so that the number can be parsed by list_to_integer
. For a dot in a leading position (except for a possible ± sign), a 0
is inserted in the string before the dot – thus, as for the rest of the reals, list_to_float
is called to obtain the number.
A string that is not matched by any of the possible regex patterns is handled by to_number
by throw
ing an exception. The value ''
(an empty atom) is passed along with the exception, but as explained above, that value actually is insignificant.
Each of the three calls of match
produces a triple when the match is successful, and another value if it is not. The components of those triples are unimportant – it only matters whether the match
succeeds – so the case
expressions use the coarsest triple-matching patterns ({_,_,_}
) for guarding the corresponding actions.
-module(rpn). -export([main/0]). -import(io,[get_line/1,write/1,nl/0]). -import(string,[len/1,chr/2,substr/2,substr/3,tokens/2]). -import(regexp,[match/2]). main() -> case get_line('') of eof -> init:stop(); S -> evalrpn(tokens(S," \t\n")), main() end. evalrpn([]) -> ok; evalrpn(Tks) -> write(try lists:foldl( fun (Tk,Stk) -> Ix = chr("+-*/",hd(Tk)), if Ix>0, length(Tk)==1 -> [Y,X|Z] = Stk, [erlang:(list_to_atom(Tk))(X,Y) | Z]; true -> [to_number(Tk) | Stk] end end, [],Tks) of [X] -> X; _ -> error catch _:_ -> error end), nl(). to_number(S) -> case match(S,"^[+-]?[0-9]+\\.?$") of {_,_,_} -> I = len(S), list_to_integer(substr(S,1,I-chr(S,$.) div I)); _ -> case match(S,"^[+-]?\\.[0-9]+$") of {_,_,_} -> I = if hd(S)/=$+,hd(S)/=$- -> 1; true -> 2 end, list_to_float(substr(S,1,I-1)++"0"++substr(S,I)); _ -> case match(S,"^[+-]?[0-9]+\\.[0-9]+$") of {_,_,_} -> list_to_float(S); _ -> throw('') end end end.
boykobbatgmaildotcom