<aside> 💡 Trees with an arbitrary number of children (subtrees) in each node are called general trees

</aside>

What’s the difference?

• For a binary arithmetic expression, we defined a structure with three fields: the operation, the first argument, and the second argument.
• For a general arithmetic expression, we define a structure with two fields: the operation and a list of arguments (which is a list of arithmetic expressions)

Recall…

;; A binary arithmetic expression (BinExp) is one of:
;; * a Num
;; * a BINode

(define-struct binode (op left right))
;; A Binary arithmetic expression Internal Node (BINode)
;;     is a (make-binode (anyof '* '+ '/ '-) BinExp BinExp)

Now let’s represent general trees:

;; An Arithmetic Expression (AExp) is one of:
;; * Num
;; * OpNode

(define-struct opnode (op args))
;; An OpNode (operator node) is a
;; (make-opnode (anyof '* '+) (listof AExp))

Developing eval and apply

;; (eval exp) evaluates the arithmetic expressions exp.

;;  Examples:
(check-expect (eval 5) 5)
(check-expect (eval (make-opnode '+ (list 1 2 3 4))) 10)
(check-expect (eval (make-opnode '+ (list 1
																					(make-opnode '* (list 2 3)
																					3))) 10)

;; eval: AExp -> Num
(define (eval exp)
	(cond [(number? exp) exp]
				[(opnode? exp) (apply (opnode-op exp)
											 (opnode-args exp))]))

;; (apply op args) applies the arithmetic operator op to args

;; Examples:
(check-expect (apply '+ (list 1 2 3 4)) 10)
(check-expect (apply '+ (list 1 (make-opnode '* (list 2 3)))) 7)

;; apply: (anypf 'O '*) (listof AExp) -> Num
(define (apply op args)
	(cond [(empty? args) (cond [(symbol=? op '+) 0]
														 [(symbol=? op '*) 1])]
			  [(symbol=? op '+) (+ (eval (first args))
														 (apply op (rest args)))]
				[(symbol=? op '*) (* (eval (first args))
														 (apply op (rest args)))]))