Lisp Stack Functions by Shane Zentz

; Shane Zentz
; C-311
; Homework # 9

; return the root of the subtree (function from class)
(defun root (T)
(if T (car T)))
root

; return the left sub tree (function from class)
(defun left_subtree (T)
(if (and (cdr T))
(car (cdr T))))
left_subtree

; return the right subtree (function from class)
(defun right-subtree (T)
(if (> (length T) 2)
(car (cdr (cdr T)))))
right-subtree

; tree from class
(setq S '(23 (51 (18) (33 (5))) (7 () (10))))
(23 (51 (18) (33 (5))) (7 nil (10)))

; print function from class
(defun my-print (&rest L)
(mapc 'princ L))
my-print

; print tree in symmetric order (left, root, right)
(defun print-symm (T)
(if T
(progn
(print-symm (left_subtree T))
(my-print (root T) " ")
(print-symm (right-subtree T)))))
print-symm

; testing the print-symm function....
(print-symm S)
18 51 5 33 23 7 10 nil

; iterative version of print-symm
(defun print-symm2 (T)
(let ((stackT nil) (locT nil) (frame nil) (state nil))
(push (cons T 'root) stackT)
(while stackT
(setq frame (pop stackT))
(setq locT (car frame) state (cdr frame))
(if locT
(cond ((eq state 'root)
(push (cons locT 'left) stackT)
(push (cons (left_subtree locT) 'root) stackT))
((eq state 'left)
(push (cons locT 'right) stackT)
(my-print (root locT) " "))
((eq state 'right)
(push (cons (right-subtree locT) 'root) stackT)))))))
print-symm2

(print-symm2 S)
18 51 5 33 23 7 10 nil

; optimized version (for extra credit)))))))))))))))))))
(defun print-symm3 (T)
(let ((stackT ()) (locT T))
(while locT
(push locT stackT)
(setq locT (left_subtree locT)))
(while stackT
(setq locT (pop stackT))
(my-print (root locT) " ")
(setq locT (right-subtree locT))
(while locT
(push locT stackT)
(setq locT (left_subtree locT))))))
print-symm3

(print-symm3 S)
18 51 5 33 23 7 10 nil


;rewrite of function to display state of the stack
;from function 2.....
(defun print-state (T)
(let ((stackT nil) (locT nil) (frame nil) (state nil))
(push (cons T 'root) stackT)
(while stackT
(setq frame (pop stackT))
(setq locT (car frame) state (cdr frame))
(my-print "state = " state "\n")
(my-print "stack = " stackT "\n")
(if locT
(cond ((eq state 'root)
(push (cons locT 'left) stackT)
(push (cons (left_subtree locT) 'root) stackT))
((eq state 'left)
(push (cons locT 'right) stackT)
(princ "root = " )(my-print (root locT) " " "\n"))
((eq state 'right)
(push (cons (right-subtree locT) 'root) stackT)))))))
print-state


(print-state S)
state = root
stack = nil
state = root
stack = (((23 (51 (18) (33 (5))) (7 nil (10))) . left))
state = root
stack = (((51 (18) (33 (5))) . left) ((23 (51 (18) (33 (5))) (7 nil (10))) . left))
state = root
stack = (((18) . left) ((51 (18) (33 (5))) . left) ((23 (51 (18) (33 (5))) (7 nil (10))) . left))
state = left
stack = (((51 (18) (33 (5))) . left) ((23 (51 (18) (33 (5))) (7 nil (10))) . left))
root = 18
state = right
stack = (((51 (18) (33 (5))) . left) ((23 (51 (18) (33 (5))) (7 nil (10))) . left))
state = root
stack = (((51 (18) (33 (5))) . left) ((23 (51 (18) (33 (5))) (7 nil (10))) . left))
state = left
stack = (((23 (51 (18) (33 (5))) (7 nil (10))) . left))
root = 51
state = right
stack = (((23 (51 (18) (33 (5))) (7 nil (10))) . left))
state = root
stack = (((23 (51 (18) (33 (5))) (7 nil (10))) . left))
state = root
stack = (((33 (5)) . left) ((23 (51 (18) (33 (5))) (7 nil (10))) . left))
state = root
stack = (((5) . left) ((33 (5)) . left) ((23 (51 (18) (33 (5))) (7 nil (10))) . left))
state = left
stack = (((33 (5)) . left) ((23 (51 (18) (33 (5))) (7 nil (10))) . left))
root = 5
state = right
stack = (((33 (5)) . left) ((23 (51 (18) (33 (5))) (7 nil (10))) . left))
state = root
stack = (((33 (5)) . left) ((23 (51 (18) (33 (5))) (7 nil (10))) . left))
state = left
stack = (((23 (51 (18) (33 (5))) (7 nil (10))) . left))
root = 33
state = right
stack = (((23 (51 (18) (33 (5))) (7 nil (10))) . left))
state = root
stack = (((23 (51 (18) (33 (5))) (7 nil (10))) . left))
state = left
stack = nil
root = 23
state = right
stack = nil
state = root
stack = nil
state = root
stack = (((7 nil (10)) . left))
state = left
stack = nil
root = 7
state = right
stack = nil
state = root
stack = nil
state = root
stack = (((10) . left))
state = left
stack = nil
root = 10
state = right
stack = nil
state = root
stack = nil
nil