#lang racket
(require test-engine/racket-tests)
(provide in->pre)
(define (valid e)
  (match e
    [`(,x + ,y ...) (and (valid x) (valid y))]
    [`(,x * ,y ...) (and (valid x) (valid y))]
    [x (or (symbol? x) (number? x)
           (and (list? x) (= (length x) 1) (valid (car x))))]))

(define (in->pre-h s mr acc)
  (cond
    [(empty? s) (append acc `(,(append '(*) mr)))]
    [(or (number? s) (symbol? s)) (append acc `(,(append '(*) (append mr `(,s)))))]
    [(list? (car s)) (in->pre-h (cdr s) (append mr (list (in->pre (car s)))) acc)]
    [(equal? (car s) '+) (in->pre-h (cdr s) '() (append acc `(,(append '(*) mr))))]
    [(equal? (car s) '*) (in->pre-h (cdr s) mr acc)]
    [(or (number? (car s)) (symbol? (car s))) (in->pre-h (cdr s) (append mr `(,(car s))) acc)]
    [else (error "bad expression")]))

(define (remove-unnecessary s tl)
  (cond
    [(empty? s) '()]
    [(number? s) s]
    [(symbol? s) s]
    [(and tl (list? s) (= (length s) 2)) (remove-unnecessary (cadr s) #t)]
    [(list? (car s)) (cons (remove-unnecessary (car s) #t) (remove-unnecessary (cdr s) #f))]
    [else (cons (car s) (remove-unnecessary (cdr s) #f))]))

(define (in->pre s)
  (if (not (valid s))
      (error "bad expression")
      (remove-unnecessary `(+ ,@(in->pre-h s '() '())) #t)))

(define (read-to-list)
  (define k (read))
  (if (eof-object? k)
      '()
      (cons k (read-to-list))))

;;(in->pre (read-to-list))
;; simple tests
(check-expect (in->pre '(1 + 1)) '(+ 1 1))
(check-expect (in->pre '(2 * 2)) '(* 2 2))
(check-expect (in->pre '(2 * 2 + 2)) '(+ (* 2 2) 2))
(check-expect (in->pre '(1 + 2 + 3 * 4 * 5 + 6 * 7)) '(+ 1 2 (* 3 4 5) (* 6 7)))
(check-expect (in->pre '(1 + (2 + 3 + 4))) '(+ 1 (+ 2 3 4)))
(check-expect (in->pre '((1 + (2 + 3 + 4)) * 5)) '(* (+ 1 (+ 2 3 4)) 5))

;; annoying tests
(check-expect (in->pre '(2 + ((2)))) '(+ 2 2))
(check-expect (in->pre '(1 + ((2)) + x)) '(+ 1 2 x))
(check-expect (in->pre 4) 4)
(check-expect (in->pre 'x) 'x)
(check-expect (in->pre '(x * (y + z))) '(* x (+ y z)))
(check-expect (in->pre '(x * ((y + z)))) '(* x (+ y z)))
(test)