Ladies_Man

RPN

Dec 26th, 2013
203
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scheme 1.86 KB | None | 0 0
  1. (define (list-head xs i S)
  2.   (if (= i 0) S (list-head (cdr xs) (- i 1) (append S (list (car xs))))))
  3.  
  4. (define (priority a)
  5.   (if (equal? a '*) 2 (if (equal? a '/)
  6.                            3
  7.                            (if (equal? a '+)
  8.                                 0
  9.                                 (if (equal? a '-)
  10.                                     0
  11.                                     100)))))
  12.  
  13. (define (operator? a)
  14.   (or (equal? a '<) (< (priority a) 100)))
  15.  
  16. (define (delete< xs S)
  17.   (if (null? xs) S (if (equal? (car xs) '<)
  18.                        (delete< (cdr xs) S)
  19.                        (delete< (cdr xs) (append S (list (car xs)))))))
  20.  
  21. (define (ejection x stack)
  22.    (if (null? stack) 0 (if (or (operator? x) (equal? x '>))
  23.                            (let ((k (car stack)))
  24.                            (if (equal? k '<)
  25.                                (length stack)
  26.                                (if (equal? x '>)
  27.                                    (ejection x (cdr stack))
  28.                                    (if (<= (priority x) (priority k))
  29.                                        (ejection x (cdr stack))
  30.                                         (length stack)))))
  31.                         (length stack))))
  32.  
  33. (define (rpn xs)
  34.   (define (iter xs out stack)
  35.     (if (null? xs)
  36.         (append out (delete< stack '()))
  37.         (let* ((a (car xs))
  38.            (l (cdr xs))
  39.            (k (if (and (not (null? stack)) (equal? a (car stack))) (length stack) (ejection a stack)))
  40.            (nstek (list-tail stack (- (length stack) k)))
  41.            (nstek (if (equal? a '>) (cdr nstek) nstek))
  42.            (newstek (if (operator? a) (cons a nstek) nstek))
  43.            (stack+ (list-head stack (- (length stack) k) '())))
  44.           (iter l (append out (if (and (not (equal? a '>)) (not (operator? a))) (list a) '()) stack+) newstek))))
  45.   (iter xs '() '()))
Advertisement
Add Comment
Please, Sign In to add comment