About me

About me

Feeds

RSS feed

Infix to prefix

28th August 2014

I recently wanted to allow users to enter an expression in infix notation, and then convert it to prefix notation so I could use Lisp to evaluate it. To avoid reinventing the wheel I searched for an existing solution -  you'd think it would be easy to find an off-the-shelf Lisp program convert from infix to prefix, but surprisingly I found it difficult to find anything satisfactory.

My first attempt was the prefix->infix routine from Norvig's classic book "Paradigms of Artificial Intelligence Programming" [1]. This uses a pattern matching routine he develops in an earlier chapter to match elements of the expression and build up the prefix form, and works quite well, but fails to give the correct result in some situations; for example:

CL-USER 1 > (eval (infix->prefix '(10 - 3 - 2 - 1)))
8
The answer should be 4. It parses repeated signs in the wrong order:
CL-USER 2 > (infix->prefix '(10 - 3 - 2 - 1))
(- 10 (- 3 (- 2 1)))

Next I searched on Google, but most of the solutions were either over-complicated or too fully-featured. There's a nice Lisp infix-to-prefix reader macro by Mark Kantrowitz [2], but it did far more than I needed for my application.

The implementation

The approach I finally chose was based on a neat solution I found in the book Lisp by Winston and Horn [3].

Here's my version of the routine. It currently handles the four basic arithmetic operators, and power: 

(defparameter *binary-operators* '((+ 1 +) (- 1 -) (* 2 *) 
                                   (x 2 *) (/ 2 %) (^ 3 expt)))
(defparameter *unary-operators* '((+ 4 +) (- 4 -)))

(defun weight (c) (second (assoc c *binary-operators*)))

(defun binary-opcode (c) (third (assoc c *binary-operators*)))

(defun unary-opcode (c) (third (assoc c *unary-operators*)))

(defun infix-prefix (ae)
  (cond ((atom ae) ae)
        (t (inf-aux ae nil nil))))

(defun inf-aux (ae operators operands)
  (cond
   ;; Unary operator
   ((and (atom (car ae)) (assoc (car ae) *unary-operators*))
    (inf-iter (cddr ae) operators (cons
                                   (list
                                    (unary-opcode (car ae))
                                    (infix-prefix (cadr ae))) operands)))
   (t (inf-iter (cdr ae) operators (cons (infix-prefix (car ae)) operands)))))

(defun inf-iter (ae operators operands)
  (cond 
   ((and (null ae) (null operators)) (car operands))
   ;; Implicit multiplication
   ((and ae
         (or (listp (car ae))
             (null (weight (car ae)))))
    (inf-iter (cons '* ae) operators operands))
   ((and ae
         (or (null operators)
             (> (weight (car ae)) (weight (car operators)))))
    (inf-aux (cdr ae) (cons (car ae) operators) operands))
   (t 
    (inf-iter ae (cdr operators) 
              (cons (list (binary-opcode (car operators))
                          (cadr operands) (car operands)) (cddr operands))))))

This one gets it right:

CL-USER 3 > (eval (infix-prefix '(10 - 3 - 2 - 1)))
4
Here's the converted expression:
CL-USER 4 > (infix-prefix '(10 - 3 - 2 - 1))
(- (- (- 10 3) 2) 1)

It also handles unary - and +, and implicit multiplication:

CL-USER 5 > (infix-prefix '(- 2 a + b))
(+ (* (- 2) A) B)

  1. ^ Norvig, Peter. Paradigms of Artificial Intelligence Programming. San Francisco: Morgan Kaufmann Publishers, Inc, 1992. 240.
  2. ^ Infix reader-macro by Mark Kantrowitz
  3. ^ Winston, Patrick Henry and Berthold Klaus Paul Horn. Lisp (Second Edition). Massachusetts: Addison-Wesley Publishing Company, 1984. 185.

blog comments powered by Disqus