;; Struttura dati "Espressioni RPN" -- e relativi postfissi
;;
;;   Liste Scheme


;; Struttura dati "Stack"
;;
;; Operazioni:
;;
;;   (empty-stack)                  :  -> pila
;;
;;   (empty? <stack>)               :  pila -> booleano
;;
;;   (top <stack>)                  :  pila -> elemento
;;
;;   (push <item> <stack>)          :  elemento x pila -> pila
;;
;;   (pop <stack>)                  :  pila -> pila
;;
;;   (compute <operation> <stack>)  :  operazione x pila -> pila


;; Valutazione di espressioni RPN


(define eval-rpn  ; valore numerico
  (lambda (exp)   ; exp espressione RPN
    (compute-on-stack exp (empty-stack))
    ))

(define compute-on-stack  ; valore numerico
  (lambda (exp stk)       ; exp espressione RPN, stk stack
    (if (null? exp)
        (top stk)
        (compute-on-stack
         (cdr exp)
         (let ((itm (car exp)))
           (if (number? itm)
               (push itm stk)
               (compute (get-operator itm) stk))
               ))
           )
    ))


(define get-operator  ; valore procedurale
  (lambda (itm)       ; itm simbolo atomico
    (cond ((equal? itm '+) +)
          ((equal? itm '-) -)
          ((equal? itm '*) *)
          ((equal? itm '/) quotient)
          )
    ))


;; Realizzazione della struttura dati "Stack"


(define empty-stack (lambda () null))

(define empty? null?)

(define top car)

(define push cons)

(define pop cdr)

(define compute
  (lambda (op stk)
    (let ((2nd (car stk)) (1st (cadr stk)))
      (cons (op 1st 2nd) (cddr stk)))
    ))


;; Varianti: polimorfismo della procedura di valutazione.
;;
;; Calcolo di valori numerici e di strutture che rappresentano
;; espressioni in altre notazioni.

;; Variante 1

(define get-operator          ; valore procedurale
  (lambda (itm)               ; itm simbolo atomico
    (eval itm)
    ))

;; Esercizio: qual'e' la differenza sostanziale rispetto
;; alla precedente definizione di "get-operator" ?

;; Variante 2

(define get-operator          ; valore procedurale
  (lambda (itm)               ; itm simbolo atomico
    (lambda (x y)
      (list x itm y))         ; notazione infissa
    ))

;; Variante 3

(define get-operator          ; valore procedurale
  (lambda (itm)               ; itm simbolo atomico
    (lambda (x y)
      (list itm x y))         ; notazione prefissa (Scheme)
    ))

;; Esercizio: qual e' il risultato della valutazione
;;
;;   (eval (eval-rpn <espressione RPN>))
;;
;; con questa definizione di "get-operator" ?

;; Variante 4

(define get-operator          ; valore procedurale
  (lambda (itm)               ; itm simbolo atomico
    (lambda (x y)
      (eval (list itm x y)))  ; numero
    ))


;; Valutazione di espressioni infisse


(define eval-infix
  (lambda (exp)
    (if (number? exp)
        exp
        ((eval (cadr exp))
         (eval-infix (car exp))
         (eval-infix (caddr exp))
        ))
    ))


;; Traduzione da forma infissa a forma RPN


(define infix->rpn
  (lambda (exp)
    (if (number? exp)
        (list exp)
        (append
         (infix->rpn (car exp))
         (infix->rpn (caddr exp))
         (list (cadr exp))
        ))
    ))


;; Esempi:
;;
;;  (eval-infix '((((9 - 3) + ((3 * 8) / 6)) / 2) * (12 / 4)))
;;
;;  (infix->rpn '((((9 - 3) + ((3 * 8) / 6)) / 2) * (12 / 4)))