t3x.org / sketchy / prog / infix.html
SketchyLISP Stuff Copyright (C) 2006 Nils M Holm

infix

Conformance: sketchy

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

  ; Operator symbols
  ((+ '+) (- '-) (* '*) (/ '/) (^ '^) ([ '[) (] '])

  ; Function->operator translation
  (ops '((+ . +) (- . -) (* . *) (quotient . /) (expt . ^)))

  ; Precedence list (descending order)
  (precedence '((high) (expt) (* quotient) (+ -) (low)))

  (function? (lambda (x)
    (member x '(+ - * quotient expt))))

  ; Has the function associated with 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))
            (cond ((member y (car l)) #f) (#t #t)))
          ((member y (car l)) #f)
          (#t (hp x y (cdr l)))))))
      (hp x y precedence))))

  (parenthesize (lambda (x) (append '([) x '(]))))

  (inf (lambda (x op)
    (cond ((number? x)
        ; Number: remove positive sign
        (list (normalize x)))
      ((symbol? x) (list x))
      ((function? (car x))
        ; Convert prefix to infix
        (let ((sub (append (inf (cadr x) (car x))
                     (list (cdr (assoc (car x) ops)))
                     (inf (caddr x) (car x)))))
          ; If the surrounding operation has a higher
          ; precedence, parenthesize this expression
          (cond ((higherprec? op (car x))
              (parenthesize sub))
            (#t sub))))
      (#t (bottom (list 'syntax: x)))))))

  (inf x 'low)))

Example:

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