;;; A semi-hack to implement a simple expression parsers and evaluator
;;;
;;; Here's the basic grammar:
;;;   Exp ::= Term ExpHelper
;;;   ExpHelper ::= epsilon
;;;              |  AddOp Term ExpHelper
;;;   Term ::= Factor TermHelper
;;;   TermHelper ::= epsilon
;;;               |  MulOp Factor TermHelper
;;;   Factor ::= OPEN Exp CLOSE
;;;           |  NUMBER
;;;
;;; exp, term, and factor are implemented as Scheme procedures that
;;; take one parameter, a list of characters, and returns a pair of parameters:
;;; the list after the thing is consumed and the value.
;;;
;;; exphelper and termhelper are implemented as procedures that take
;;; one parameter: a pair of list and value, and return the same
;;; kind of pair as the other procedures.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Interface

;;; Procedure:
;;;   evaluate
;;; Parameters:
;;;   str, a string
;;; Purpose:
;;;   To evaluate the arithmetic expression given by str.
;;; Produces:
;;;   value, integer.
;;; Preconditions:
;;;   str is a valid arithmetic expression using the operators
;;;   +,-,*,/, parentheses, and single-digits numbers.
;;; Postconditions:
;;;   value is the value of the arithmetic expression using
;;;   precedence.
(define evaluate
  (lambda (str)
    (cdr (eexp str))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Testing

;;; Procedures:
;;;   eexp
;;;   efact
;;;   eterm
;;; Parameter:
;;;   str, a string
;;; Purpose:
;;;   Test exp, factor, and term, respectively.
;;; Produces:
;;;   a pair, (chars . value)
;;; Preconditions:
;;;   str must represent a valid arithmetic expression (or at
;;;   least the start of one).
;;; Postconditions:
;;;   

(define eexp
  (lambda (str)
    (exp (string->list str))))

(define efact
  (lambda (str)
    (factor (string->list str))))

(define eterm
  (lambda (str)
    (term (string->list str))))

(define exp
  (lambda (chars)
    (if (null? chars)
        (error "The empty string cannot be an expression")
        (exphelper (term chars)))))

(define exphelper
  (lambda (pair)
    (let ((chars (car pair))
          (val1 (cdr pair)))
      (if (and (not (null? chars)) (add-op? (car chars)))
          (let ((pair2 (term (cdr chars))))
            (exphelper (cons (car pair2) 
                              ((operator (car chars)) val1 (cdr pair2)))))
          pair))))

(define term
  (lambda (chars)
    (if (null? chars)
        (error "The empty string cannot be a term")
        (termhelper (factor chars)))))

(define termhelper
  (lambda (pair)
    (let ((chars (car pair))
          (val1 (cdr pair)))
      (if (and (not (null? chars)) (mul-op? (car chars)))
          (let ((pair2 (factor (cdr chars))))
            (termhelper (cons (car pair2) 
                              ((operator (car chars)) val1 (cdr pair2)))))
          pair))))

(define factor
  (lambda (chars)
    (cond
      ((null? chars) (error "Expecting a factor, found nothing!"))
      ((char-numeric? (car chars))
       (cons (cdr chars)
             (string->number (string (car chars)))))
      ((char=? (car chars) #\()
       (let ((pair (exp (cdr chars))))
         (if (char=? (caar pair) #\))
             (cons (cdar pair) (cdr pair)))))
      (else
       (error 
        (string-append "Expecting a term; saw '" 
                       (list->string (car pair))
                       "'"))))))

(define add-op?
  (lambda (ch)
    (and (char? ch) 
         (or (char=? ch #\+)
             (char=? ch #\-)))))

(define mul-op?
  (lambda (ch)
    (and (char? ch) 
         (or (char=? ch #\*)
             (char=? ch #\/)))))


(define operator
  (lambda (ch)
    (cond
      ((char=? ch #\+) +)
      ((char=? ch #\*) *)
      ((char=? ch #\/) /)
      ((char=? ch #\-) -)
      (else (error (string-append "Invalid operator: " (string ch)))))))

(define test1
  (lambda ()
    (factor (string->list "2+3"))))

(define test2
  (lambda ()
    (exp (string->list "1"))))

(define test3
  (lambda ()
    (term (string->list "2+3"))))

(define test4
  (lambda ()
    (exp (string->list "1+2"))))