Contents    Page-10    Prev    Next    Page+10    Index   

Converting a Tree to RPN


(defun tree-to-polish (exp)
  (nreverse (tree-to-p exp nil)))

(defun tree-to-p (exp result)
  (if (atom exp)         ; if leaf
      (cons exp result)  ; push
      (progn
        (mapc #'(lambda (opnd) ; operands
                  (setq result
                        (tree-to-p opnd
                                   result)))
              (rest exp))
        (cons (first exp) result)))) ; add op

(tree-to-polish '(+ (* a b) c))  =  (A B * C +)

(setq testx '(/ (+ (minus b)
                   (sqrt (- (expt b 2)
                            (* 4 (* a c)))))
                (* 2 a)))

(tree-to-polish testx)
 = (B MINUS B 2 EXPT 4 A C * * - SQRT + 2 A * /)