RPN Calculator in Common Lisp

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.

Within 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 rpn.

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 :no-error of handler-case receives control, binding the name r to the result. If not nil, r is printed out using write and 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.)

Note that 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 s, in 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 nil. Similarly, 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 y and 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 tk.

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.

The 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 read.

(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)

boykobbatgmaildotcom