PLACE
spec
solutions
Algol 68

RPN Calculator in Algol 68

This Algol 68 implementation consists of a main program, a recursive procedure, evalrpn, that evaluates the RPN expression, and several help procedures.

The main part of the program is the 11-lines fragment located near its end. It reads lines from the standard input, storing each one in the string s. The procedure all blank is then called to check whether s contains any non-blank characters; if so, s is passed to evalrpn. If evalrpn returns true, and if at that time s is empty, except for some whitespace, the result r of the evaluation is printed in a certain format, using the built-in functions fixed for formatting and print for printing. Getting false from evalrpn or the latter leaving s non-empty is a sign of erroneous input so then an error message is printed.

evalrpn evaluates the RPN expression recursively by extracting tokens from the end of the string. The get token procedure returns either a real number, or an integer from 1 to 4 encoding an operator +, -, *, or /, or the value empty of type void to signify an incorrect token or that there is no token at all. The type (or, in Algol 68 terms, mode) token is defined to unite these three possibilities formally. evalrpn discriminates between the three cases using a construct called conformity clause: a real value is immediately returned (in a passed-by-reference parameter), 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, and a possible false returned from such a call gets properly transferred to the upper-level caller as an error indication. When get token returns empty to evalrpn (the third, implicitly specified branch of the conformity clause), evalrpn returns a false.

get token searches backwards for a non-blank substring in the input string which is passed to it by reference through 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 get number 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. In case there was nothing but blanks left in the input string, tk is set to empty. Finally, tk gets passed back to evalrpn.

(In the call of get number, the value actually passed as an argument is not s(i+1:j) but a reference to a copy of it, generated by loc string – this is needed because get number expects a reference, and the slice s(i+1:j) is not one.)

In order to obtain a numeric value from its string argument, get number opens an input channel on the string (using the built-in procedure associate) so that the transput mechanism, namely calling get, can be used to do the conversion. However, get number has first to check whether the string to be read correctly represents a number. In particular, Algol 68 allows neither an arithmetic sign nor a trailing decimal dot in a number denotation, therefore such a string, which is perfectly acceptable by our calculator specification, would have to be adapted for reading by get.

get number checks for and removes a possible arithmetic sign from the string. Then it scans the string for correctness, i.e. to ensure that there is at least one digit, at most one decimal dot, and no other characters. A dot ending the string, if any, is removed. If the string is found correct, it is converted to a real number as described, and passed back as the result from the call. The value empty is passed in case of an erroneous string.

The program makes use of two other small procedures: is nonspace, which checks whether a character is different from a space or a tab, and search char, which searches a string for a character that satisfies a certain predicate. Another two, viz. (char c) bool: ~is nonspace(c) and (ref file f) bool: eoi := true, are anonymous procedures. The former implements a logical negation to is nonspace, while the latter is set, by a call of on logical file end, as the handler of the end-of-input event.

When read fails to get a current line because the input is exhausted, the handler is invoked. It does two things: by returning true it signals to the program that the end-of-input condition has been handled, and by assigning true to eoi it becomes possible to end the while-loop that controls the interaction, and thus to end the program. Note that simply returning true from the handler is not sufficient, as then the program would continue to attempt reading. Returning false does cause program termination, but it also invokes some (unspecified) system-defined reaction to the end-of-input condition, which we have chosen to avoid.

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:

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 below. The defining document for the language 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 program they are underlined. Most Algol 68 translators expect them to be in capital letters.

One may notice that the names of most procedures in the program contain blanks. In fact, blanks within user-defined names are not meaningful, but the programmer has the option to make use of them as he wishes.

The upb, used in several places in the program, is an operator yielding the upper bound of a string (or any array) subscript.

proc is nonspace = (char c) bool: c /= blank & c /= repr 9;

proc search char = (proc (char) bool p, ref int n, string s) void: (
  n := 0;
  for i from upb s by -1 to 1 while n = 0
    do (p(s[i]) | n := i) od
);

proc evalrpn = (ref string s, ref real r) bool: (
  mode token = union (real,int,void);

  proc get token = (ref string s) token: (
    proc get number = (ref string s) token: (
      int sgn := 1;
      (s[1]="+" or s[1]="-" | (s[1]="-" | sgn := -1); s := s(2:));
      int nd := 0;
      for i to upb s while nd<2 do
        (int dummy; ~char in string(s[i],dummy,"0123456789")
         | (s[i]="." | nd +:= 1 | nd := 2))
      od;
      (nd=1 & s[upb s]="." | s := s(:upb s-1));
      (nd<2 & upb s>0
       | file f; real x; associate(f,s); get(f,x); close(f); sgn*x
       | empty)
    );   # get number #

    token tk; int i,j;
    search char(is nonspace,j,s);
    (j>0 | search char((char c) bool: ~is nonspace(c),i,s(:j));
           int k := 0;
           tk := (j-i=1 & char in string(s[j],k,"+-*/")
                  | k
                  | get number(loc string := s(i+1:j)));
           s := s(:i)
         | tk := empty);
    tk
  );   # get token #

  token tk := get token(s);
  (tk | (real z): (r := z; true),
        (int op): (bool t; real x,y;
                   t := evalrpn(s,y); (t | t := evalrpn(s,x));
                   (t | r := (op | x+y, x-y, x*y, x/y));
                   t)
      | false)
);   # evalrpn #

bool eoi := false;
on logical file end(stand in, (ref file f) bool: eoi := true);
while ~eoi do
  proc all blank =
    (ref string s) bool: (int k; search char(is nonspace,k,s); k=0);
  string s;
  read((s,newline));
  (~all blank(s)
   | print(((real r; (evalrpn(s,r) | all blank(s) | false)
             | fixed(r,0,4) | "error"), newline)))
od

boykobbatgmaildotcom