postfix --> infix

post2i.scm

; postfix notation --> infix notation
; Compilers 1st ed. ex. 2.8 (p.79)
; Compilers 2nd ed. ex. 2.3.2 (p.60)
; https://gist.github.com/yamasushi/a333611fa259b7f60f0984ba98f5b3ec

(define-module post2i
  (export postfix->infix))
(select-module post2i)

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

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

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

(define (postfix->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
        {(digit? hd) ; <digit> 
          (let-values ([(syn xs) (R (make-string 1 hd) (cdr xs))] ) 
            (values syn xs) ) }
        {else (error "S: xs=" xs)}
      ) ) ) )

(define(R inh xs)
  ;(format #t "R inh=~s xs=~s~%" inh xs)
  (if (or (null? xs) ($ not $ digit? $ car xs) )
      (values inh xs) ; ε
      (let-values ([(s-syn xs) (S xs)])
        (cond 
          { (op? (car xs)) 
            (let-values ([
                (r-syn xs) 
                (R (string-append 
                      inh (make-string 1 (car xs)) s-syn) 
                    (cdr xs) ) ] )
              (values r-syn xs) ) }
          {else (errorf "R s-syn=~s xs=~s" s-syn xs)}
        ) ) ) )