Sexp tree to postfix op

forthify.rkt

#lang racket/base

(require racket/match)

(define (op? e)
  (match e
    [(or '+ '- '* '/) #t]
    [_ #f]))

(define (forthify e)
  (match e
    [(list (? op? o) a b)
     (combine-forth (forthify a) o b)]
    [(list (? op? o) a b c* ...)
     (for/fold ([fexpr (forthify `(,o ,a ,b))]) ([c (in-list c*)])
       (combine-forth fexpr o c))]
    [(? number? n) (list n)]
    [(? symbol? x) (list x)]))

;; combine-forth :: forth-expr op lisp-expr -> forth-expr
(define (combine-forth fexpr op expr)
  (append fexpr (forthify expr) (list op)))

(module+ test
  (require chk)

  (chk #:= (forthify '(+ 3 4)) '(3 4 +)
       #:= (forthify '(* 3 4)) '(3 4 *)
       #:= (forthify '(- 3 4)) '(3 4 -)
       #:= (forthify '(/ 3 4)) '(3 4 /)

       #:= (forthify '(+ 3 4 5)) '(3 4 + 5 +)
       #:= (forthify '(+ 3 4 5 6)) '(3 4 + 5 + 6 +)

       #:= (forthify '(+ (* 3 4) 4)) '(3 4 * 4 +)

       #:=
       (forthify '(+ a (* b (- c d) e) f))
       '(a b c d - * e * + f +)      
       )
  )