;; 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)))]))