;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; TWO PRIMITIVE FUNCTIONS USED BY THE TWO SOLUTIONS BELOW ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; apply-op takes a symbol and two numbers and applies the operator indicated by 
;; the symbol on the two numbers.  It checks whether the symbol is one of the four
;; valid operators in the language and whether a division-by-zero is occuring
(define (apply-op sym num1 num2)
  (cond ((symbol=? sym '+)
         (+ num1 num2))
        ((symbol=? sym '-)
         (- num1 num2))
        ((symbol=? sym '*)
         (* num1 num2))
        ((symbol=? sym '/)
         (if (= num2 0)
             '(E "DIVISION BY ZERO")
             (/ num1 num2)))
        (true '(E "INVALID OPERATOR"))))

;; error? checks whether the input is of the form '(E ..), which indicates an error.
;; This is primarily for passing up errors to the main routine.
(define (error? l)
  (if (empty? l) false
      (if (list? l) 
          (equal? (first l) 'E)
          (not (number? l)))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; SOLUTION 1: INTERPRETING THROUGH PARSING THE EXPRESSION ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;; eval-next-exp takes a list and evaluates the next expression in the list.
;; It returns a new list which equals the value of the next expression 
;; concatenated with the remainder of the input list.
;;
;; For example: (eval-next-exp '(+ 4 5 * 3 4)) should be '(9 * 3 4).
;;              (eval-next-exp '(- * 4 5 + * 3 2 1 11 * 9 0)) should be '(2 11 * 9 0).
;;
;; Note that the input list l is not required to be a valid expression.  If, however,
;; it is not possible to extract the next expression from the list, then eval-next-exp
;; returns an string indicating the invalidity of the expression.  
;;
;; eval-next-exp calls the functions apply-op and error? and is called by 
;; the main interpreter routine parse-interpreter.  

(define (eval-next-exp l)
    (cond 
      [(null? l) empty]
      [(number? (first l))
        (cons (first l) (rest l))]
      [true 
       (local ((define temp (eval-next-exp (rest l)))) 
         (cond [(null? temp) '(E "INVALID EXPRESSION: LACKING OPERANDS")]
               [(error? temp) temp]
               [true 
                (local ((define temp1 (eval-next-exp (rest temp))))
                  (cond [(null? temp1) '(E "INVALID EXPRESSION: LACKING OPERANDS")]
                        [(error? temp1) temp1]
                        [true 
                         (local ((define temp2 (apply-op (first l) (first temp) (first temp1))))
                           (if (error? temp2) temp2
                               (cons temp2 (rest temp1))))]))]))]))

;; parse-interpreter is the main routine, takes the input expression as a list and returns
;; the value or a string indicating the lack of validity of the expression.
(define (parse-interpreter l)
  (local ((define result (eval-next-exp l)))
    (if (error? result) 
        (second result)
        (if (null? (rest result))
              (first result)
              "INVALID EXPRESSION: LACKING OPERATORS"))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; SOLUTION 2: INTERPRETING THROUGH THE ACCUMULATOR TECHNIQUE ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; refine takes a list and repeatedly looks for patterns of the form <num> <num> <op> as the
;; first three elements of the list (that is, top of the stack).  If it finds one, then it
;; replaces the three with a single number, equal to the value of operator <op> applied on the
;; 2 numbers.  Having replaced the three terms by a single number, refine then recursively executes
;; on the new list, until no such pattern can be found.
(define (refine stack)
  (cond 
    ((>= (length stack) 3)
     (if (and (number? (first stack)) (number? (second stack)) (symbol? (third stack)))
          (local ((define result (apply-op (third stack) (second stack) (first stack))))
            (if (error? result) result
                (refine (cons result (rest (rest (rest stack)))))))
          stack))
    (true stack)))
          
;; The accumulator function takes two lists -- one called the stack which holds the 
;; evaluation of the part of the expression that has been scanned, and the other called
;; remainder which holds the part of the expression that has not been scanned.  accumulator
;; returns a single list, which is the "final value" of the stack variable after scanning
;; the entire expression.  In each recursive call, the function refine is called on
;; the stack.
(define (accumulator stack remainder)
  (local ((define newstack (refine stack)))
        (if (error? newstack)
            newstack
            (if (empty? remainder)
                newstack
                (accumulator (cons (first remainder) newstack) (rest remainder))))))

;; This is the main routine, which calls the accumulator function with an empty
;; stack and returns the value computed by the accumulator function, while also 
;; doing some tests on the validity of the expression.
(define (accum-interpreter l)
  (local ((define result (accumulator empty l)))
    (if (error? result) (second result)
        (cond
          [(empty? result) "INVALID EXPRESSION"]
          [(and (= (length result) 1) (number? (first result))) (first result)]
          [true "INVALID EXPRESSION"]))))