89 lines
No EOL
3.2 KiB
Racket
89 lines
No EOL
3.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) (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)
|
|
((alt3 (seq3 parse-mul-div (accept-itm "+") parse-add-sub)
|
|
(seq3 parse-mul-div (accept-itm "-") parse-add-sub)
|
|
parse-mul-div) lst))
|
|
|
|
(define (parse-mul-div lst)
|
|
((alt3 (seq3 parse-number (accept-itm "*") parse-mul-div)
|
|
(seq3 parse-number (accept-itm "/") parse-mul-div)
|
|
parse-number) 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)))])) |