forked from chrisstephenson/CMPE314-2016
-
Notifications
You must be signed in to change notification settings - Fork 0
/
msl-starter.plai
84 lines (69 loc) · 3.21 KB
/
msl-starter.plai
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#lang plai-typed
(define-type msl
[msl-num (n : number)]
[msl-add (lhs : msl) (rhs : msl)]
[msl-mul (lhs : msl) (rhs : msl)]
)
;; eval msl -> number
;; evaluate an msl expression
;; examples
;; (msl-num 7) -> 7
;; (msl-add (msl-num 3) (msl-num 4)) -> 7
;; (msl-add (msl-add (msl-num 3) (msl-num 4)) (msl-num 35)) -> 42
(define (eval [expr : msl])
(type-case msl expr
[msl-num (n) n]
[msl-add (lhs rhs) (+ (eval lhs) (eval rhs))]
[msl-mul (lhs rhs) (* (eval lhs) (eval rhs))]))
(test (eval (msl-num 7)) 7)
(test (eval (msl-add (msl-num 3) (msl-num 4))) 7)
(test (eval (msl-add (msl-add (msl-num 3) (msl-num 4)) (msl-num 35))) 42)
;; parse s-expression -> msl
;; convert a quoted s expression into the equivalent msl form
;; examples
;; '7 -> (msl-num 7)
;; '(+ 3 4) -> (msl-add (msl-num 3) (msl-num 4))
;; '(+ (+ 3 4) 35) -> (msl-add (msl-add (msl-num 3) (msl-num 4)) (msl-num 35))
(define (parse [s : s-expression]) : msl
(cond
[(s-exp-number? s) (msl-num (s-exp->number s))]
[(s-exp-list? s)
(let ([sl (s-exp->list s)])
(case (s-exp->symbol (first sl))
[(+) (msl-add (parse (second sl)) (parse (third sl)))]
[(*) (msl-mul (parse (second sl)) (parse (third sl)))]
[else (error 'parse "invalid list input")]))]
[else (error 'parse "invalid input")]))
(test (parse '7) (msl-num 7))
(test (parse '(+ 3 4)) (msl-add (msl-num 3) (msl-num 4)))
(test (parse '(+ (+ 3 4) 35)) (msl-add (msl-add (msl-num 3) (msl-num 4)) (msl-num 35)))
;; output-reverse-polish msl -> list of s-expression
;; output the msl as the reverse polish commands needed to evaluate it
;; examples
;; (msl-num 7) -> '(7)
;; (msl-add (msl-num 3) (msl-num 4)) -> '(4 3 +)
;; (msl-mul (msl-num 3) (msl-num 4)) -> '(4 3 *)
;; (msl-add (msl-mul (msl-num 3) (msl-num 4)) (msl-num 9)) -> '(3 4 * 9 +)
;; (msl-mul (msl-num 3) (msl-add (msl-num 4) (msl-num 9))) -> '(3 4 9 + *)
(define (output-reverse-polish [expr : msl])
(type-case msl expr
[msl-num (n) (list (number->s-exp n))]
[msl-add (lhs rhs) (append (append (output-reverse-polish lhs) (output-reverse-polish rhs))
(list (symbol->s-exp '+)))]
[msl-mul (lhs rhs) (append (append (output-reverse-polish lhs) (output-reverse-polish rhs))
(list (symbol->s-exp '*)))]))
(test (output-reverse-polish (msl-num 7)) (s-exp->list '(7)))
(test (output-reverse-polish (msl-add (msl-num 3) (msl-num 4))) (s-exp->list '(3 4 +)))
(test (output-reverse-polish (msl-mul (msl-num 3) (msl-num 4))) (s-exp->list '(3 4 *)))
(test (output-reverse-polish (msl-add (msl-mul (msl-num 3) (msl-num 4)) (msl-num 9))) (s-exp->list '(3 4 * 9 +)))
(test (output-reverse-polish (msl-mul (msl-num 3) (msl-add (msl-num 4) (msl-num 9)))) (s-exp->list '(3 4 9 + *)))
"Example outputs"
(output-reverse-polish (msl-num 7))
(output-reverse-polish (msl-add (msl-num 3) (msl-num 4)))
(output-reverse-polish (msl-mul (msl-num 3) (msl-num 4)))
(output-reverse-polish (msl-add (msl-mul (msl-num 3) (msl-num 4)) (msl-num 9)))
(output-reverse-polish (msl-mul (msl-num 3) (msl-add (msl-num 4) (msl-num 9))))
"Parser -> reverse polish output"
(output-reverse-polish (parse '(+ 99 (* 5 8))))
"Parser -> evaluation"
(eval (parse '(+ 99 (* 5 8))))