CODEWITHSUNDEEP
lispcommon-lispinfix-notation
pragmus
pragmus

Reputation: 4063

Define function for evaluating infix expressions in Lisp

I am not very good in Lisp and I need to do a function which allows evaluating of infix expressions. For example: (+ 2 3) -> (infixFunc 2 + 3). I tried some variants, but none of them was successful.

One of them:

(defun calcPrefInf (a b c)
  (funcall b a c))

Upvotes: 2

Views: 3853

Answers (5)

soulcheck
soulcheck

Reputation: 36777

Assuming that you're using a lisp2 dialect, you need to make sure you're looking up the function you want to use in the function namespace (by using #'f of (function f). Otherwise it's being looked up in the variable namespace and cannot be used in funcall.

So having the definition:

(defun calcPrefInf (a b c)
    (funcall b a c))

You can use it as:

(calcPrefInf 2 #'+ 3)

Upvotes: 0

test30
test30

Reputation: 3654

You can try http://www.cliki.net/infix. 

(nfx 1 + (- x 100)) ;it's valid!
(nfx 1 + (- x (3 * 3))) ;it's ALSO valid!
(nfx 1 + (- x 3 * 3)) ;err... this can give you unexpected behavior

Upvotes: 0

David A. Wheeler
David A. Wheeler

Reputation: 561

A different approach for "evaluating infix expressions" would be to enable infix reading directly in the Common Lisp reader using the "readable" library, and then have users use the notation. Then implement a traditional Lisp evaluator (or just evaluate directly, if you trust the user).

Assuming you have QuickLisp enabled, use:

(ql:quickload "readable")
(readable:enable-basic-curly)

Now users can enter any infix expression as {a op b op c ...}, which readable automatically maps to "(op a b c ...)". For example, if users enter:

{2 + 3}

the reader will return (+ 2 3). Now you can use:

(eval (read))

Obviously, don't use "eval" if the user might be malicious. In that case, implement a function that evaluates the values the way you want them to.

Tutorial here: https://sourceforge.net/p/readable/wiki/Common-lisp-tutorial/

Upvotes: 1

Mark Karpov
Mark Karpov

Reputation: 7599

OK, let's do it just for fun. First, let's define order of precedence for operations, since when one deals with infix notation, it's necessary.

(defvar *infix-precedence* '(* / - +))

Very good. Now imagine that we have a function to-prefix that will convert infix notation to polish prefix notation so Lisp can deal with it and calculate something after all.

Let's write simple reader-macro to wrap our calls of to-prefix, for aesthetic reasons:

(set-dispatch-macro-character
 #\# #\i (lambda (stream subchar arg)
           (declare (ignore sub-char arg))
           (car (reduce #'to-prefix
                        *infix-precedence*
                        :initial-value (read stream t nil t)))))

Now, let's write a very simple function to-prefix that will convert infix notation to prefix notation in given list for given symbol.

(defun to-prefix (lst symb)
  (let ((pos (position symb lst)))
    (if pos
        (let ((e (subseq lst (1- pos) (+ pos 2))))
          (to-prefix (rsubseq `((,(cadr e) ,(car e) ,(caddr e)))
                              e
                              lst)
                     symb))
        lst)))

Good, good. Function rsubseq may be defined as:

(defun rsubseq (new old where &key key (test #'eql))
  (labels ((r-list (rest)
             (let ((it (search old rest :key key :test test)))
               (if it
                   (append (remove-if (constantly t)
                                      rest
                                      :start it)
                           new
                           (r-list (nthcdr (+ it (length old))
                                           rest)))
                   rest))))
           (r-list   where)))

Now it's time to try it!

CL-USER> #i(2 + 3 * 5)
17
CL-USER> #i(15 * 3 / 5 + 10)
19
CL-USER> #i(2 * 4 + 7 / 3)
31/3
CL-USER> #i(#i(15 + 2) * #i(1 + 1))
34

etc.

Upvotes: 12

sheikh_anton
sheikh_anton

Reputation: 3452

If you want it to work for composite expressions like (2 + 3 * 5 / 2.4), it's better to convert it into proper prefix expression, then evaluate it. You can find some good example of code to do such convetion here: http://www.cs.berkeley.edu/~russell/code/logic/algorithms/infix.lisp or in Piter Norvigs "Paradigs of Artificial Intelligence Programming" book. Code examples here: http://www.norvig.com/paip/macsyma.lisp

It's reall too long, to be posted in the aswer.

Upvotes: 3

Related Questions