Wednesday, March 20th, 2013

Shen infix notation

shen, programming

Here’s an implementation of infix notation for Shen; it’s effectively Dijkstra’s shunting-yard algorithm.

Custom precedence can be defined by setting prec.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
(define prec
    ** -> 4
    * -> 3
    / -> 3
    + -> 2
    - -> 2)

\* power is defined in the maths library *\
(define **
    X Y -> (power X Y))

(define shunt
    [] Output [] -> Output
    [] [] [X Op Y | Rest] -> (shunt [Op] [(shunt [] [] Y) (shunt [] [] X)] Rest) where (element? Op [+ - * / **])
    [] [] X -> X
    [Op | Ops] [Y X] [] -> (shunt Ops [Op X Y] [])
    [Op2 | Ops] [Y X | R] [Op1 Z | Rest] ->
        (let Nout (if (> (prec Op1) (prec Op2))
                    [[Op1 Y (shunt [] [] Z)] X | R]
                    [(shunt [] [] Z) [Op2 X Y] | R])
            Nops (if (> (prec Op1) (prec Op2))
                    [Op2 | Ops]
                    [Op1 | Ops])
            (shunt Nops Nout Rest)) where (element? Op1 [+ - * / **]))

(defmacro infix-macro
    [in | X] -> (shunt [] [] X))

It can be called as follows:

1
(in (2 + 3) * 4)

Comments

comments powered by Disqus