102 lines
No EOL
4.2 KiB
Racket
102 lines
No EOL
4.2 KiB
Racket
;; The first three lines of this file were inserted by DrRacket. They record metadata
|
|
;; about the language level of this file in a form that our tools can easily process.
|
|
#reader(lib "htdp-advanced-reader.ss" "lang")((modname infix-parser-left-assoc-2) (read-case-sensitive #t) (teachpacks ((lib "gui.rkt" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "gui.rkt" "teachpack" "htdp")) #f)))
|
|
(define (alt2 parser1 parser2)
|
|
(lambda (lst)
|
|
(cond [(not (empty? (parser1 lst))) (parser1 lst)]
|
|
[else (parser2 lst)])))
|
|
|
|
(define (alt3 parser1 parser2 parser3)
|
|
(lambda (lst)
|
|
(cond [(not (empty? (parser1 lst))) (parser1 lst)]
|
|
[(not (empty? (parser2 lst))) (parser2 lst)]
|
|
[else (parser3 lst)])))
|
|
|
|
(define (seq2 parser1 parser2)
|
|
(lambda (lst)
|
|
(cond [(empty? (parser1 lst)) empty]
|
|
[(empty? (parser2 (second (parser1 lst)))) empty]
|
|
[else (list (list (first (parser1 lst))
|
|
(first (parser2 (second (parser1 lst)))))
|
|
(second (parser2 (second (parser1 lst)))))])))
|
|
|
|
(define (seq3 parser1 parser2 parser3)
|
|
(lambda (lst)
|
|
(cond [(empty? (parser1 lst)) empty]
|
|
[(empty? (parser2 (second (parser1 lst)))) empty]
|
|
[(empty? (parser3 (second (parser2 (second (parser1 lst)))))) empty]
|
|
[else (list (list (first (parser1 lst))
|
|
(first (parser2 (second (parser1 lst))))
|
|
(first (parser3 (second (parser2 (second (parser1 lst)))))))
|
|
(second (parser3 (second (parser2 (second (parser1 lst)))))))])))
|
|
|
|
(define (accept-itm itm)
|
|
(lambda (lst)
|
|
(cond [(empty? lst) empty]
|
|
[(equal? (first lst) itm) (list itm (rest lst))]
|
|
[else empty])))
|
|
|
|
(define (accept-digit)
|
|
(lambda (lst)
|
|
(cond [(empty? lst) empty]
|
|
[(or (equal? "0" (first lst))
|
|
(equal? "1" (first lst))
|
|
(equal? "2" (first lst))
|
|
(equal? "3" (first lst))
|
|
(equal? "4" (first lst))
|
|
(equal? "5" (first lst))
|
|
(equal? "6" (first lst))
|
|
(equal? "7" (first lst))
|
|
(equal? "8" (first lst))
|
|
(equal? "9" (first lst)))
|
|
(list (first lst) (rest lst))]
|
|
[else empty])))
|
|
|
|
(define (accept-empty)
|
|
(lambda (lst)
|
|
(cond [(empty? lst) (list empty empty)]
|
|
[else empty])))
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(define (infix->prefix str)
|
|
(infix->prefix-expl (explode str)))
|
|
|
|
(define (infix->prefix-expl lst)
|
|
(cond [(empty? (parse-add-sub lst)) empty]
|
|
[else (tree->prefix (first (parse-add-sub lst)))]))
|
|
|
|
(define (parse-add-sub lst)
|
|
(parse-add-sub-x (second (parse-mul-div lst))
|
|
(first (parse-mul-div lst))))
|
|
|
|
(define (parse-add-sub-x lst expr)
|
|
(cond [(not (empty? ((accept-itm "+") lst))) (parse-add-sub-x (second (parse-mul-div (second ((accept-itm "+") lst))))
|
|
(list expr "+" (first (parse-mul-div (second ((accept-itm "+") lst))))))]
|
|
[(not (empty? ((accept-itm "-") lst))) (parse-add-sub-x (second (parse-mul-div (second ((accept-itm "-") lst))))
|
|
(list expr "-" (first (parse-mul-div (second ((accept-itm "-") lst))))))]
|
|
[else (list expr lst)]))
|
|
|
|
(define (parse-mul-div lst)
|
|
(parse-mul-div-x (second (parse-number lst))
|
|
(first (parse-number lst))))
|
|
|
|
(define (parse-mul-div-x lst expr)
|
|
(cond [(not (empty? ((accept-itm "*") lst))) (parse-mul-div-x (second (parse-number (second ((accept-itm "*") lst))))
|
|
(list expr "*" (first (parse-number (second ((accept-itm "*") lst))))))]
|
|
[(not (empty? ((accept-itm "/") lst))) (parse-mul-div-x (second (parse-number (second ((accept-itm "/") lst))))
|
|
(list expr "/" (first (parse-number (second ((accept-itm "/") lst))))))]
|
|
[else (list expr lst)]))
|
|
|
|
(define parse-number (accept-digit))
|
|
|
|
|
|
(define (tree->prefix tree)
|
|
(cond [(string? tree) tree]
|
|
[else (string-append (second tree)
|
|
(tree->prefix (first tree))
|
|
(tree->prefix (third tree)))])) |