Inorder

There are several ways of writing arithmetic expressions; these are closely related to the orders of tree traversal:

• Prefix or Cambridge Polish, as in Lisp: (+ x y)

• Infix, as in Java: x + y

• Polish Postfix: x y +

An expression tree can be printed as infix by an inorder traversal:

(defun op  (x) (first x))    ; access functions
(defun lhs (x) (second x))   ; left-hand side
(defun rhs (x) (third x))    ; right-hand side

(defun infix (x)
  (if (consp x)
      (progn (princ "(")
             (infix (lhs x))    ; first child
             (prin1 (op x))     ; parent
             (infix (rhs x))    ; second child
             (princ ")") )
      (prin1 x)))

>(infix '(* (+ x y) z))
((X+Y)*Z)