O.K, I have a function I threw together to translate prefix notation to
reverse polish notation. It works fine for small, simple functions, but
it is so recursive that it might blow up on more complex expressions.
Trace has already run out of stack space when I run
? (makeRPN (/ (- b (sqrt (- * b b) (* 4 (* a c))))) (* 2 a)))
So, my question is, can anyone tell me how to go about making this less
nasty? Size really matters far more than speed in this case. No, this
isn't homework.
(defun RPN (lst &optional (thestream (make-string-output-stream)))
(labels ((write-args (obj outstream)
(RPN (car obj) outstream)
(if (cdr obj)
(write-args (cdr obj) outstream))
outstream))
(if (consp lst)
(progn
(write-args (cdr lst) thestream)
(princ (car lst) thestream)
(princ " " thestream))
(progn
(princ lst thestream)
(princ " " thestream))))
thestream)
(defmacro makeRPN (lst &optional (thestream (make-string-output-stream)))
`(get-output-stream-string
(RPN (quote ,lst) ,thestream)))
P.S. Is there anywhere I can look to get hints on optimizing the RPN
which is spat out? i.e., tanslating "B B" into "B DUP" etc.
B.B. --I am not a goat!
Bryant Brandon (········@airmail.net) wrote:
: O.K, I have a function I threw together to translate prefix notation to
: reverse polish notation. It works fine for small, simple functions, but
: it is so recursive that it might blow up on more complex expressions.
: Trace has already run out of stack space when I run
: ? (makeRPN (/ (- b (sqrt (- * b b) (* 4 (* a c))))) (* 2 a)))
: So, my question is, can anyone tell me how to go about making this less
: nasty? Size really matters far more than speed in this case. No, this
: isn't homework.
Something like:
(defun prind (x)
(prin1 x)
(princ " "))
(defun op (expr)
(first expr))
(defun args (expr)
(rest expr))
(defun to-rpn (expr)
(cond ((atom expr) (prind expr))
(t (mapc #'to-rpn (args expr))
(prind (op expr)))))
: P.S. Is there anywhere I can look to get hints on optimizing the RPN
: which is spat out? i.e., tanslating "B B" into "B DUP" etc.
Any book on compilers should cover this.
P.