infix

Language: R5RS Scheme

Purpose: Convert arithmetic expressions from prefix to infix notation. Prefix expressions may contain variables (symbols like X), numbers (quoted integer numbers like -57), and these functions: + - * quotient expt.
Functions are translated to these operators: + - * / ^.
 
For instance,
(infix '(+ -15 17))
gives
(-15 + 17).
 
Infix will insert brackets ([ and ]) as required.

Arguments:
X - arithmetic expression

Implementation:

(define (infix x)
  (letrec
    ; Function->operator translation
    ((ops '((+ . +)
            (- . -)
            (* . *)
            (quotient . /)
            (expt . ^)))
     ; Precedence list in descending order
     (precedence
       '((high) (expt) (* quotient) (+ -) (low)))
     (function?
       (lambda (x)
         (member x '(+ - * quotient expt))))
     ; Has the operator X a higher precedence than Y?
     (higherprec?
       (lambda (x y)
         (letrec
           ((hp (lambda (x y l)
              (cond ((null? l) #f)
                ((member x (car l))
                  (not (member y (car l))))
                ((member y (car l)) #f)
                (else (hp x y (cdr l)))))))
           (hp x y precedence))))
     (parenthesize
       (lambda (x)
         (append '([) x '(]))))
     (_infix
       (lambda (x outer-op)
         (cond ((number? x) (list x))
           ((symbol? x) (list x))
           ((function? (car x))
             ; Convert prefix to infix
             (let ((sub-expr (append (_infix (cadr x) (car x))
                               (list (cdr (assoc (car x) ops)))
                               (_infix (caddr x) (car x)))))
               ; If the surrounding operation has a higher
               ; precedence, parenthesize this expression
               (cond ((higherprec? outer-op (car x))
                   (parenthesize sub-expr))
                 (else sub-expr))))
           (else (bottom (list 'syntax: x)))))))
    (_infix x 'low)))

Example:

(infix '(+ 12 (* 3 (expt 4 (+ 5 6))))) 
=> (12 + 3 * 4 ^ [ 5 + 6 ])