So today someone on a mailing list asked for help with a postfix to expression-tree converter. While he hasn’t responded to me yet, I thought I’d share my solution on here. It was surprisingly easy to write in Scheme. Please feel free to comment if you have suggestions.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | ; define a tree structure to work with (define (make-tree val left right) (list val left right)) (define (value tree) (car tree)) (define (left-branch tree) (cadr tree)) (define (right-branch tree) (caddr tree)) ; converts postfix list to an expression-tree (define (postfix-to-tree ops) (define (postfix-iter symbols values) ;progress through symbols keeping a list of values (if (null? symbols) (car values) ; returning end result (let ((x (car symbols))) (cond ((number? x) (postfix-iter (cdr symbols) (cons x values))) (else (postfix-iter (cdr symbols) (cons (make-tree x (cadr values) (car values)) (cddr values)))))))) (postfix-iter ops '())) ;(postfix-to-tree '(2 1 + 3 4 * +)) == (+ (* 4 3) (+ 1 2)) |
Also, suppose rather than making an expression tree, we wanted to evaluate the postfix instead?
We could just eval the output of postfix-to-tree, i.e. (eval (postfix-to-tree ‘(2 1 + 3 4 * +))), but in general I think it’s preferred to avoid eval.
So alternatively, we’ll write a function to evaluate the symbols, and make a minor change to our main function and we’re there.
24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | (define (eval-op op a b) (cond ((eq? '+ op) (+ a b)) ((eq? '- op) (- a b)) ((eq? '* op) (* a b)) ((eq? '/ op) (/ a b)))) ; evaluates postfix-expression (define (eval-postfix ops) (define (postfix-iter symbols values) ;progress through symbols keeping a list of values (if (null? symbols) (car values) ; returning end result (let ((x (car symbols))) (cond ((number? x) (postfix-iter (cdr symbols) (cons x values))) (else (postfix-iter (cdr symbols) (cons (eval-op x (cadr values) (car values)) (cddr values)))))))) (postfix-iter ops '())) ; (eval-postfix '(2 1 + 3 4 * +)) == 15 |
These solutions could probably use a little error-checking, but they both operate correctly on valid input and get the job done.
