The main procedure,
rpn, reads an input line into the string
s and passes it to
eval-rpn for evaluating the RPN expression. For ease of further processing, tab characters in
s are replaced by spaces.
eval-rpn, expression evaluation progresses through extracting tokens one at a time and analyzing each one. The input string is correspondingly shortened after each extraction. A stack of intermediate values
st is maintained along the process. For obtaining and working on each new token
eval-rpn calls itself again with updated input string and stack.
St is an optional argument to
eval-rpn defaulting to an empty list. The default value is only used as an initial one in the call from
If a syntax error is found in the RPN expression, a
signal is issued with the predefined condition name
error as an argument. Nesting the call of
eval-rpn within a call of
handler-case results in trapping the signal by the (only) error clause of
handler-case, which to this end is labeled the same way as the signal:
error. Handling the signal consists of printing an error message.
If an RPN expression is evaluated successfully, the keyword-labeled clause
handler-case receives control, binding the name
r to the result. If not
r is printed out using
terpri (the latter being for terminate print line).
Float is applied on
r before actually printing it, because
r may happen to be a rational number, and we want to print all results as floats; if
float is omitted, only those results that really are not rational will print in decimal-dot notation. (Lisp guarantees an exact rational result for any arithmetic computation, provided that none of the participating numbers is a floating-point one.)
r indeed can be
nil, and this happens if and only if the input line contained no tokens at all.
Whatever the outcome of the evaluation,
rpn proceeds to call itself again so that reading and evaluation are repeated.
Read-line reports end-of-input to
rpn by returning the value
nil instead of an actual string. That value is detected by means of the
null predicate, so that if
(null s) holds,
rpn does nothing but return.
Obtaining a token within
eval-rpn begins by stripping the string
s off any possible initial blank characters. Thus, if
s then becomes empty, there are no (more) tokens to be processed and the procedure concludes by popping the result of evaluation off the stack and returning it. The stack, however, can be empty – if the input line was initially empty or all-blanks – and then the procedure returns
nil, since that is the value returned by
pop for an empty stack. More than one item present in the stack is an indication of an RPN syntax error, which is properly signaled.
For a non-empty
i we find the position one after the first token in
s (which is either the first blank from the beginning of the string, or the index immediately past the end of
s if there are no blanks). The token is stored in
tk and subjected to qualification tests.
(The use of
or here is a typical example of how a seemingly boolean operation is in fact a control construct:
or evaluates its arguments in sequence and stops as soon as it finds one with a non-
nil value, then it returns that value. It will only return
nil when all its arguments are
and evaluates until an argument is found that is
nil, and it only returns a non-
nil when that is the value of its last argument, and none of the preceding ones is
nil. Scheme is very similar in this respect.)
Discrimination between the cases of an arithmetic operator, a number, and anything else for
tk takes place within a
cond (conditional) form. In the first clause of
cond, besides checking whether
tk represents an operator, by calling
second it is made sure that the stack contains (at least) two numbers necessary to apply the operation on. Applying itself is done by calling
funcall on the values
x popped off the stack. Note that
read-from-string is used to obtain the respective atom from the string
tk. This is needed because that atom is the only means to refer to the function performing the operation whose name is
The result of applying an arithmetic operator
tk, or the number represented by
tk itself, eventually becomes the result of
cond and so gets pushed onto the stack. If
tk is neither of these, the third clause of
cond is reached, and as it is guarded by a constantly true expression (
t), an error signal is issued.
get-number procedure finds out whether a token parses as a numeric value, returning that value on success and
nil if parsing fails. It does that by testing the kinds and the number of characters of each kind in the token. More precisely,
get-number ensures that there is at least one digit, at most one decimal dot, a possible leading arithmetic sign, and no other characters in the string. Obtaining the number from an already proven correct string is done by calling
read-from-string, as described above for the kind of atom representing an operator.
Read-from-string is a representative of the so called reader mechanism of Lisp, which is indeed a lexer: it is used for lexical analysis on strings, including mapping the recognized tokens to (Lisp) data objects. We could have implemented the calculator using as a tokenizer another, more general Lisp procedure called
read. Successive calls of
read applied on an input stream which appears to be a string will extract tokens from that stream until the latter is exhausted. Potentially, this could have saved us the labour of extracting individual tokens and finding out what data object each one represents. In practice, however, this does not work easily. As
read is a Lisp-oriented tokenizer, it will try to recognize tokens as defined in the Lisp language, entirely skipping comments and admitting a wide range of number representations: all these must be treated as errors in the calculator. Therefore some additional work is needed in order to warrant against such errors, eventually canceling out the benefits of using
(defun get-number (s) (let* ((i (if (find (elt s 0) "+-") 1 0)) (d (count-if 'digit-char-p s :start i)) (f (count #\. s :start i))) (and (> d 0) (< f 2) (= (+ i f d) (length s)) (read-from-string s)))) (defun eval-rpn (s &optional (st '())) (let ((s (string-left-trim " " s))) (if (string/= s "") (let* ((i (or (position #\Space s) (length s))) (tk (subseq s 0 i))) (eval-rpn (subseq s i) (push (cond ((and (= 1 (length tk)) (find (elt tk 0) "+-*/") (second st)) (let* ((y (pop st)) (x (pop st))) (funcall (read-from-string tk) x y))) ((get-number tk)) (t (signal 'error))) st))) (if (second st) (signal 'error) (pop st))))) (defun rpn () (let ((s (read-line *standard-input* nil))) (unless (null s) (handler-case (eval-rpn (nsubstitute #\Space #\Tab s)) (:no-error (r) (when r (write (float r)) (terpri))) (error () (write-line "error"))) (rpn)))) (rpn)