gistfile1.scm

;; Adam Coffman
;; Scheme assignment 3 

;; The PARSE function accepts as argument an infix arithmetic expression in the
;; form of a list and returns a list representation of the corresponding expresion
;; tree.  Ex., (parse '(3 + 4))--> (+ (3 4)), 
;; (parse '(3 + 4 * 5)) --> (+ (3 (* (4 5)))) and
;; (parse '( 4 + 3 * ( 5 + 6) - 2)) --> (- ((+ (4 (* (3 (+ (5 6)))))) 2))
;; Note that each element of the list must be one of three things: a number; one of +, -, *
;; /; or a sublist (ex., (5 + 6)) 
;; The resulting tree is represented as a list in the form of 
;; (op (left-subtree right-subtree))
;; where the 1st element is the root (and an operator), and the 2nd element 
;; is a list of the left and right subtree.  Note that any of the tree or subtree could be
;; a number

;; Your mission: 
;; 1. Study/scan the parse and findop functions
;; 2. Complete the sublist function as described below (40 easy points)
;; 3. Write a function COMPUTE accept a list representation of an
;;    arithmetic expression tree, evaluate it, return the result. (40 easy points again) 
;;    For example:
;;    (compute '(+ (3 4))) --> 7
;;    (compute '(- ((+ (4 (* (3 (+ (5 6)))))) 2)))--> 35
;; 
;; This assignment is due 11:00 AM Thursday (10/9/2008).  


(define parse
  (lambda (exp)
    (cond ((number? exp) exp) 
          ((null? exp) #f)
          ((= (length exp) 1) (parse (car exp)))
          (else (let ((pos (findop exp)) (left '()) (right '()))
                      (set! left (parse (sublist exp 0 (- pos 1)))) 
                      (set! right (parse (sublist exp (+ pos 1) (- (length exp) 1))))
                  (list (list-ref exp pos) (list left right)) 
                )
          )
     )
  )
) ;; end of parse

(define findop
  (lambda (lst)
    (do ((pos 0 (+ 1 pos)) (L lst (cdr L)) (bestv 0) (best 0) (curv 0))
        ((null? L) best)
        (cond ((or (equal? '+ (car L)) (equal? '- (car L))) 
               (set! curv 2))
              ((or (equal? '* (car L)) (equal? '/ (car L))) 
               (set! curv 1))
              (else (set! curv 0))
        )
        (if (>= curv bestv) 
            (begin (set! bestv curv) (set! best pos)))
        
    )
   )
)
  
;; sublist accepts 3 arguments: a list; a integer BEGIN position; and- a
;; integer END.  It returns a sublist which contains the top-level elements from
;; BEGIN position to END position in the orginal order.  For example,
;; (sublist '(a b c d e) 2 3) --> (c d)
;; (sublist '(a b c d e) 4 3) --> ()
;; (sublist '( 4 + 3 * ( 5 + 6) - 2) 0 4) --> (4 + 3 * (5 + 6))
(define sublist
  (lambda (lst begin end)
    (strip-front (strip-end lst (- (length lst) end ) 1) begin 0)
   )
  )

;;Helper function, used to strip "num" elements off the front of the 
;;list. count is used as a counter and should always be passed in as 0.
;;(strip-front '(1 2 3 4 5) 2 0) -> (3 4 5)
(define strip-front
  (lambda (lst num count)
    (if (equal? num count) lst (strip-front (cdr lst) num (+ count 1)))
  )
)

;;Helper function, same as strip-front but takes elements off the back
;;of the list.
(define strip-end
  (lambda (lst num count)
    (reverse (strip-front (reverse lst) num count))
  )
)

;;Works as explained in the assignment.
(define compute
  (lambda (lst)
    (cond ((list? (car lst)) (compute (car lst))) 
         ((integer? (car lst)) (car lst))
         (else ((eval(car lst)) (compute(cadr lst)) (compute(cdadr lst))))
         )
   )
)