prefix --> infix

pre2i.scm

; prefix notation ---> infix notation
; https://gist.github.com/yamasushi/2f940393e46de5c4f90422047f8ce267

(define-module pre2i
  (export prefix->infix))
(select-module pre2i)

; S -> <op> S S | <digit>

(define digit? #[0-9])
(define op?    #[+\-*/] )

(define (prefix->infix str)
  (let-values ([(syn xs) (S (string->list str))])
    (format #t "syn=~s xs=~s~%" syn xs)
    syn ) )

(define (S xs)
  (format #t "S xs=~s~%" xs)
  (if (null? xs)
    (error "S xs=" xs)
    (let1 hd (car xs)
      (cond
        { (op? hd) 
          (let-values   ([(left  xs) (S (cdr xs))])
            (format #t "left=~s xs=~s~%" left xs)
            (let-values ([(right xs) (S xs)])
              (format #t "right=~s xs=~s~%" right xs)
              (values
                (string-append left (make-string 1 hd) right) xs) ) ) }
        { (digit? hd)
          (values (make-string 1 hd) (cdr xs) ) } 
        { else (error "S: xs=" xs) }  ) ) ) )