;; Dato astratto "Albero binario"
;;
;; Alberi binari non vuoti: un nodo e' considerato equivalente
;; all'albero che contiene solo quel nodo-foglia
;;
;; Operazioni:
;;
;;   (leaf-tree <item>)                :  nodo -> albero
;;
;;   (leaf? <tree>)                    :  albero -> booleano
;;
;;   (grow-tree <item> <tree> <tree>)  :  nodo x albero x albero -> albero
;;
;;   (root-node <tree>)                :  albero -> nodo
;;
;;   (left <tree>)                     :  albero -> albero
;;
;;   (right <tree>)                    :  albero -> albero


;; Realizzazione:

(define leaf-tree
  (lambda (node) (cons node null))
  )

(define leaf?
  (lambda (tree) (null? (cdr tree)))
  )

(define grow-tree
  (lambda (root lft rgt)
    (cons root (cons lft rgt))
    ))

(define root-node car)

(define left cadr)

(define right cddr)


;; Applicazione degli alberi binari:
;; alberi di valutazione di espressioni.

;; Visita simmetrica dell'albero di valutazione:
;; espressione in forma infissa.

(define tree->inexp
  (lambda (e-tree)
    (if (leaf? e-tree)
        (number->string (root-node e-tree))
        (string-append
         "("
         (tree->inexp (left e-tree))
         (symbol->string (root-node e-tree))
         (tree->inexp (right e-tree))
         ")"
         )
        )
    ))


;; Visita posticipata dell'albero di valutazione:
;; espressione in forma Polacca inversa.

(define tree->rpn
  (lambda (e-tree)
    (if (leaf? e-tree)
        (string-append
         (number->string (root-node e-tree))
         " ")
        (string-append
         (tree->rpn (left e-tree))
         (tree->rpn (right e-tree))
         (symbol->string (root-node e-tree))
         " ")
        )
    ))


;; Esempio: valutazione di espressioni RPN
;; e costruzione di alberi di valutazione


;; Modifica della procedura "compute-on-stack":

(define compute-on-stack
  (lambda (exp stk)
    (if (null? exp)
        (top stk)
        (compute-on-stack
         (cdr exp)
         (let ((itm (car exp)))
           (if (number? itm)
               (push (get-number itm) stk)        ; modifica
               (compute (get-operator itm) stk))
               ))
           )
    ))


(define get-number  ; forma standard e varianti 1-4
  (lambda (itm)     ; itm numerico
    itm             ; numero e relativa rappresentazione
    ))              ; sono in generale entita' distinte


;; Polimorfismo della procedura di valutazione:
;; calcolo di alberi di valutazione di espressioni.

;; Variante 5

(define get-number
  (lambda (itm)      ; itm numerico
    (leaf-tree itm)  ; foglia
    ))

(define get-operator        ; valore procedurale
  (lambda (itm)             ; itm simbolo atomico
    (lambda (x y)
      (grow-tree itm x y))  ; albero binario
    ))


;; Ulteriore esempio.

;; Lettura di un'espressione infissa con parentesi
;; ridondanti e costruzione dell'albero di valutazione

(define inexp->tree  ; parametro implicito: standard input
  (lambda ()
    (let ((tkn (token)))                ; lettura di un token
      (cond ((number? tkn)              ; numero?
             (leaf-tree tkn)            ; costante numerica
             )
            ((left-par? tkn)            ; parentesi aperta?
             (let ((1st (inexp->tree))  ; sottoespressione sinistra
                   (op (token))         ; operazione
                   (2nd (inexp->tree))  ; sottoespressione destra
                   (last-tkn (token))   ; parentesi chiusa
                   )
               (grow-tree op 1st 2nd))  ; albero di valutazione
             )
            (else (unknown-symbol tkn)) ; errore
            )
    )))


(define unknown-symbol
  (lambda (tkn)
    "?"
    ))


;; lettura, riconoscimento e rappresentazione di un token
;; Come si potrebbe saltare gli eventuali spazi bianchi?

(define token  ; parametro implicito: standard input
  (lambda ()
    (let ((ch (read-char)))
      (cond ((char-numeric? ch) (read-number (digit ch)))
            ((equal? ch #\+) '+)
            ((equal? ch #\-) '-)
            ((equal? ch #\*) '*)
            ((equal? ch #\/) '/)
            ((equal? ch #\() 'lp)
            )
    )))

(define left-par?
  (lambda (tkn)
    (equal? tkn 'lp)
    ))


;; Valore numerico di una cifra

(define digit
  (lambda (ch)
    (- (char->integer ch) (char->integer #\0))
    ))


;; Lettura, riconoscimento e rappresentazione di un numero
;; procedura basata sulla ricorsione di coda

(define read-number  ; parametro implicito: standard input
  (lambda (n)        ; n: valore parziale gia' calcolato
    (if (char-numeric? (peek-char))
        (read-number (+ (* 10 n) (digit (read-char))))
        n
        )
    ))