RPN Calculator in Scheme

Of the four procedures in this implementation, all but get-number are recursive, and the first and the fourth are tail-recursive, which Scheme is guaranteed to transform to iterative internally. read-tokens reads and tokenizes an input line, eval-expr parses and evaluates it, and the main procedure, rpn, is responsible for calling the latter two and printing the results. get-number is a parser for numbers. rpn gets called in the last line to start the program.

Scheme has no built-in procedure to read an entire line of text, even of known or limited length. Instead, our procedure read-tokens reads a line character by character and tokenizes it, returning a reversed list of lists of characters representing the tokens. For example, if the input is 2.7 3 +, it returns ((#\+) (#\3) (#\2 #\. #\7)). As reading advances, the resulting list grows by adding nested lists (tokens) to its front. Tokens themselves grow by adding characters to their front, but finally the normal order of characters within each token is restored by calling (map reverse …).

Thus, read-tokens returns an expression in ‘reversed-reversed Polish notation’, which is then passed to eval-expr for evaluation. For empty input lines our tokenizer returns an empty list, (), and on end of input it returns #f, representing ‘false’.

eval-expr evaluates its input recursively. It checks to find whether the first token in the list represents a number. To this end it calls get-number, which returns either a number or #f. If the token does not represent a number (y is #f), it is checked if it is an operator. By that time, if the token's first character is one of + - * /, then op is a pair of that character and the corresponding symbol, e.g. (#\+ . +), and if the token does not start as an operator, then op is #f. Therefore tk is an operator if both op is not #f and tk consists of a single character.

If tk is an operator, eval-expr calls itself to find the values of the corresponding operands. (That evaluation may fail due to shortage of numbers in the RPN expression, in which case a #f is returned.) Finally, the operation is evaluated; the operator symbol is obtained as the second entry (cdr) of the op pair, from which eval finds the respective arithmetic procedure.

When the evaluation is successful, eval-expr returns a list with the computed value as the head, and the part of the eval-expr's argument list that remained unused in the evaluation as the tail. Those residuals are used as arguments in the calls of eval-expr to itself. Also, in rpn, we check whether the residual for the entire expression is empty; if that is not the case, the expression is syntactically incorrect.

This coupling of a numeric result with the still unused tokens of an RPN expression is needed in order to represent the state of its evaluation as a single value, but it is somewhat unnatural and leads to cluttering up the essential processing with list construction/deconstruction actions. A possible alternative is to use multiple values: a device that allows more than one value to be bundled together without creating an explicit data structure for that. However, Scheme's support for handling multiple values is only rudimentary, and in fact hardly applicable here.

Scheme' built-in procedure string->number computes a number from its string representation and returns #f if the string fails to parse as a number, but it is designed to handle a syntactically wider class of numbers (including rational, for example), and so cannot directly serve our needs. The get-number procedure does the necessary parsing explicitly, and only when it succeeds in that it calls string->number to actually obtain the number. get-number takes account of a possible arithmetic sign and ensures that among the remaining characters there is at least one digit, at most one decimal dot, and no other characters.

To enforce the result of an expression to be displayed as a real number in rpn, and not a rational one, there is the inexact built-in procedure used which does the necessary numeric type transformation.

In several places in eval-expr we use and for conditional evaluation: this built-in procedure returns the value of its last argument or #f if any of them evaluates to #f. In the latter case, the arguments following the first #f are not evaluated. Thus, e.g. (and e1 e2) is equivalent to (if e1 e2 #f). The or procedure works similarly.

(define (read-tokens css)
  (let ((c (read-char)))
    (cond ((eof-object? c) #f)
          ((char=? c #\newline)
              (map reverse (if (null? (car css)) (cdr css) css)))
          ((char-whitespace? c)
              (read-tokens (if (null? (car css)) css (cons '() css))))
          (else (read-tokens (cons (cons c (car css)) (cdr css)))))))

(define (get-number s)
  (let ((d 0) (f 0)
        (q (if (let ((c (car s))) (or (char=? c #\+) (char=? c #\-)))
              (cdr s) s)))
    (for-each
      (lambda (c)
        (cond ((char=? c #\.) (set! f (+ 1 f)))
              ((memq c (string->list "0123456789")) (set! d (+ 1 d)))
              (else (set! f 2))))
      q)
    (and (> d 0) (< f 2) (string->number (list->string s)))))

(define (eval-expr css)
  (and (pair? css)
    (let* ((tk (car css)) (css (cdr css))
           (y (get-number tk))
           (op (assoc (car tk) '((#\+ . +) (#\- . -) (#\* . *) (#\/ . /)))))
      (if y
        (cons y css)
        (and op (= 1 (length tk))
          (let ((y (eval-expr css)))
            (and y (let* ((css (cdr y)) (x (eval-expr css)))
                     (and x (cons ((eval (cdr op)) (car x) (car y)) (cdr x)))))))))))

(define (rpn)
  (let ((css (read-tokens '(()))))
    (if css
      (begin
        (if (pair? css)
          (let ((v (eval-expr css)))
            (display (if (and v (null? (cdr v)))
                        (inexact (car v)) "error"))
            (newline)))
        (rpn)))))

(rpn)

boykobbatgmaildotcom