PLACE |
spec |
solutions |
Snobol |
Snobol excels at string pattern matching and replacement, and it is natural to make use of this in implementing an RPN calculator. We can replace simple subexpressions – ones of the form number-number-operator – directly in the input string with their result. Thus, by doing purely textual transformations, the input line gradually reduces to a string containing a single number. By ‘purely textual’ I mean that in the process of expression evaluation no data structure is used, explicit or implicit, other than the input line itself. Of course individual computations on pairs of numbers resort to doing arithmetics as usual.
First, we define, in a set of patterns, the grammar of the parts we are going to match and replace. This includes the syntax of a number, with or without a decimal point and an arithmetic sign.
d
, op
, ws
, sp1
, sp0
, int
, num
, and xpr
all are pattern variables, with values defined by expressions made up of pattern-valued operators and built-in functions. (Other such functions are used elsewhere in the program.) d
, op
, and ws
are patterns that match a single digit, an operator, and a whitespace, respectively. sp1
matches one or more whitespace characters, while sp0
matches either this or an empty string. num
is the pattern for a number (using int
for a digit sequence), and xpr
matches a string of two numbers followed by an operator. xpr
is so construced that these three matched parts are stored in the variables x
, y
, and o
. After the operator, the pattern matches either trailing blanks (sp1
) or the end of the string (rpos(0)
).
At the statement labeled read
, a line gets read in the variable line
or, failing that due to encountering end of input, the control is transfered to the end
label, thus halting the program. The next operator matches line
against an empty (or blank-only) content, and if that succeeds, reading is repeated.
A non-empty input string containing a dot character not preceded by digits but followed by at least one is modified by appending a zero character in front of the dot – this is what the statement labeled zapp
does. The said replacement is necessary because Snobol refuses to treat a string starting with .
as a number. The zapp
statement jumps back to itself, so it is executed once for every such number. The variables p
and q
keep and restore the context of the matched part each time there is indeed a match.
The statement labeled doop
matches a subexpression, possibly preceded by blanks in line
, eval
uates it, and puts the result back in place of the matched part. The argument to eval
is a string, representing a valid expression in Snobol. The string is the result of concatenating, with intervening blanks, the values of x
, o
, and y
, as bound by the current matching of xpr
. In order to ensure that floating-point (and not integer) arithmetic is performed, the value of x
is forced to a ‘real’ number by adding a zero of that type to it.
Each succesful match within doop
loops back to the same statement for trying another match. When no further match is possible, the statement that follows attempts to match line
against a single number, possibly with leading/trailing blanks but nothing else in the string. Upon success the number is printed out by bindind the standard output channel output
to the matched part of line
, just as if a variable is being bound. If the match fails, meaning that the input RPN expression was syntactically icorrect, an error message is printed by the next statement – output
is being used as if it were a string variable whose value gets replaced. Either way, control is eventually passed back to reading the next input line.
d = '0123456789'; op = any('+-*/'); ws = ' ' char(9) sp1 = span(ws); sp0 = sp1 | '' int = span(d) num = (any('+-') | '') int ('.' (int | '') | '') xpr = num . x sp1 num . y sp1 op . o (sp1 | rpos(0)) read line = input :f(end) line pos(0) sp0 rpos(0) :s(read) zapp line (pos(0) | notany(d)) . p '.' any(d) . q + = p '0.' q :s(zapp) doop line sp0 xpr = ' ' eval(x + 0. ' ' o ' ' y) ' ' :s(doop) line pos(0) sp0 (num . output) sp0 rpos(0) :s(read) output = 'error' :(read) end
boykobbatgmaildotcom