PLACE |
spec |
solutions |
Algol 68 |
This Algol 68 implementation consists of a main part, a recursive procedure evalrpn
that evaluates an RPN expression, and some help procedures.
The main part is a loop near the end of the text starting at the label rep
. It reads lines from the standard input, storing each one in the string variable s
. The call of nonblank
checks whether its argument contains any non-blank characters, i.e., is nonempty. If so, s
is passed to evalrpn
. If evalrpn
does return and by that time s
does not contain any unprocessed leftover, the result r
of evaluating the arithmetic expression in s
is appropriately formatted and printed. Then a goto
command loops back to rep
so that another input line may be processed.
The program is terminated upon ending the standard input by an implicit call of the procedural argument of on logical file end
. That procedure has, by way of a requirement, a bool
return type, but all it actually does is pass control to the stop
label which the language defines to be implicitly present at the end of the program text. Thus on logical file end
sets an end-of-input event handler that happens to end the program execution as well.
As seen in this program, the goto
word is optional in Algol 68: a label name itself acts as a control transfer command. Thus stop
is really goto stop
and rep
is goto rep
, but omitting the goto
, beside tightening the text, has the effect of making the label names look as if they themselves are commands. This also applies to the label err
which is referred to at several places.
evalrpn
evaluates the RPN expression recursively by extracting tokens from the end of the string. The gettoken
procedure returns either a real number or an integer from 1 to 4 encoding an operator: +
, -
, *
, or /
. The type (or, in Algol 68 terms, mode) token
is defined to unite these two possibilities formally. evalrpn
discriminates between the two cases using a construct called a conformity clause. In it, a real value is immediately returned, whereas an integer 1-4 is mapped to its corresponding operation, x+y
etc., by means of a case clause. The values x
and y
of the two operands are obtained through calls of evalrpn
to itself.
gettoken
searches backwards for a nonblank substring in the input string which is passed to it by evalrpn
. If it finds one, it sets the value of tk
of type token
correspondingly: if the substring is an operator character, it is encoded by its position k
within the string "+-*/"
, otherwise getnumber
is called which tries to parse the substring s[i+1:j]
as a number. The input string is then reduced by removing the just analysed part of it, and tk
gets passed back to evalrpn
. In the calls of nonblank
and getnumber
where a slice of s
is passed as an argument the value actually passed is a reference to a copy (generated by loc string
) of the respective slice. This is necessary because each of the called procedures needs a reference and a slice is not one. loc
is the way to generate an anonymous variable dynamically on the program stack.
In order to obtain a numeric value from its string argument, getnumber
opens an input channel on the string (using the built-in procedure associate
) so that a built-in procedure, get
in this case, can be used to do the conversion as if through reading from a file. However, getnumber
has first to check whether the string to be read correctly represents a number. To this end it ensures that there is at least one digit, at most one decimal dot, and no other characters. In addition, getnumber
strips the string off a possible arithmetic sign and a trailing decimal dot because these, although correct according to our calculator specification, are not allowed in a number denotation by Algol 68.
Eventually, getnumber
either returns a real number if one can be read off the string, or does not return at all. In the latter case it passes control to the label err
in the main part of the program, so that an error message is printed before possibly processing a new input line. So does gettoken
when it cannot detect a token in the input string. As a result, a missing or incorrect token causes getnumber
or gettoken
, and thus all nested recursive calls of evalrpn
, to abort immediately and yield control to err
.
The text of the program is probably more easily read with the knowledge of the following syntactic conveniences of Algol 68 that are made use of:
begin
and end
to enclose any of them, but (
and )
are also accepted.if
…then
…fi
or if
…then
…elif
…else
…fi
, but also accepted are (
…|
…)
and (
…|
…|:
…|
…)
, respectively.(
…|
…,
…,
…)
for case
…in
…,
…,
…esac
, and similarly for conformity clauses.For example, here is how nonblank
searches backwards for a nonblank or blank character (depending on the value of b
) in s
. If the index is already 0
, the search ends without success, and 0
— an invalid index — is produced and hence returned. If n
is positive and s[n]
is what is searched for, the index n
is produced and returned. Otherwise, n
decreases and the control is passed back to tst
so that the tests are repeated with the new n
.
Also unusual is upb
, seen at several places in the program. It is an operator yielding the upper bound of a string's (or any array's) subscript.
The names of the procedures char in string
and on logical file end
, and that of the channel stand in
contain blanks. Blanks within names are not meaningful in Algol 68, but may be used for better readability.
Certain identifiers are predefined in Algol 68 and form a separate namespace from the rest. The same applies to the identifiers that designate user-defined types (modes), such as token
in this program. The language definition prescribes that these special names be represented in a way that distinguishes them in the text, but it is not specific about how to do that. In this implementation of the calculator they are underlined. Most Algol 68 translators expect them to be in capital letters.
proc nonblank = (ref string s, bool b) int: ( int n := upb s; tst: (n = 0 | 0 |: b /= (s[n] = blank or s[n] = repr 9) | n | n -:= 1; tst) ); proc evalrpn = (ref string s) real: ( mode token = union (real,int); proc gettoken = (ref string s) token: ( proc getnumber = (ref string s) real: ( int sgn := 1; (s[1] = "+" or s[1] = "-" | (s[1] = "-" | sgn := -1); s := s[2:]); int nd := 0, dummy; for i to upb s while nd < 2 do (~char in string(s[i],dummy,"0123456789") | (s[i] = "." | nd +:= 1 | nd := 2)) od; (nd = 1 and s[upb s] = "." | s := s[:upb s-1]); (nd < 2 and upb s > 0 | file f; real x; associate(f,s); get(f,x); close(f); sgn*x | err) ); # getnumber # int j = nonblank(s,true); (j = 0 | err); int i = nonblank(loc string := s[:j], false); token tk := (int k := 0; j-i = 1 and char in string(s[j],k,"+-*/") | k | getnumber(loc string := s[i+1:j])); s := s[:i]; tk ); # gettoken # (gettoken(s) | (real z): z, (int op): (real y := evalrpn(s); real x := evalrpn(s); (op | x+y, x-y, x*y, x/y))) ); # evalrpn # string s; on logical file end(stand in, (ref file f) bool: stop); rep: read((s,newline)); (nonblank(s,true) > 0 | real r = evalrpn(s); (nonblank(s,true) > 0 | err); print((fixed(r,0,4),newline))); rep; err: print(("error",newline)); rep
boykobbatgmaildotcom