[ikarus-users] shunting-yard

[Eduardo Cavazos]

Hello,

Below is a Scheme version of the shunting yard algorithm as explained on 
this page:

    http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

Example:

    > (infix 3 + 4 * 5 - 6 ^ 7 + 8)
    (+ (- (+ 3 (* 4 5)) (^ 6 7)) 8)

Would you write it differently? If so, and you care to share, let's see!

Ed

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(import (only (srfi :1) circular-list))


(define precedence-table
  '((sentinel . 0)
    (+        . 1)
    (-        . 1)
    (*        . 2)
    (/        . 2)
    (^        . 3)))

(define (precedence item)
  (cdr (assq item precedence-table)))


(define (operator? obj)
  (member obj '(+ - * / ^)))


(define (shunting-yard expr operands operators)

  (define (apply-operator)
    (shunting-yard expr
                   (cons (list (car operators)
                               (list-ref operands 1)
                               (list-ref operands 0))
                         (cdr (cdr operands)))
                   (cdr operators)))

  (if (null? expr)

      (if (eq? (car operators) 'sentinel)
          (car operands)
          (apply-operator))

      (let ((elt (car expr)))

        (if (operator? elt)

            (if (> (precedence elt)
                   (precedence (car operators)))

                (shunting-yard (cdr expr) operands (cons elt operators))

                (apply-operator))

            (shunting-yard (cdr expr) (cons elt operands) operators)))))


(define-syntax infix

  (syntax-rules ()

    ( (infix elt ...)
      (shunting-yard '(elt ...) '() (circular-list 'sentinel)) )))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;