Lab 3: A Postfix Interpreter
Bard College – Computer Science – Design of Programming Languages

In this week’s lab we will create a program — another meta-program — to evaluate programs written in postfix notation. Postfix programs look a little strange, although, maybe not that strange after a few weeks of Lisp. Postfix notation puts the operator after the operands. So 2 + 3 would be 2 3 + and (18 + 2) / 4 is represented by  18 2 + 4 /. This is known as Reverse Polish Notation

The magic of postfix is that it is relatively easy to evaluate expressions using a single stack; very little parsing or parentheses. Forth, Postscript, and Joy all use postfix notation, and the Java virtual machine is stack-based. Try it out on on repl.it.

# ​​Postfix Warm-Up

Evaluating expressions written in postfix is relatively straightforward using a stack. Procedures (i.e., operators) take their input (i.e. operands) from the stack (pop), and put their output on the stack (push). Most things that are not procedures, like numbers, are pushed onto the stack. More details can be found hetre

The following stack operations would occur when evaluating 18 2 + 4 /

​​make-stack      --> '()
​​push 18         --> '(18)
​​push 2          --> '(2 18)
​​v1 = pop        --> '(18)    v1=2
​​v2 = pop        --> '()      v2=18
​​push v2 + v1    --> '(20)
​​push 4          --> '(4 20)
​​v3 = pop        --> '(20)    v3=4
​​v4 = pop        --> '()      v4=20
​​push v4 / v3    --> '(5)

Evaluate 18 2 + 4 / using the following stack;  document how make-stack works.

​​ (define (make-stack)
​​   (let ((s '()))
​​     (lambda (cmd . rest)
​​        (cond  ((eq? 'top cmd)      (car s))
​​               ((eq? 'display cmd)  (begin (display s) (newline))))
​​               ((eq? 'push cmd)     (set! s (cons (car rest) s)))
​​               ((eq? 'pop cmd)      (let ((v (car s))) (begin (set! s (cdr s)) v)))
​​               (else                (error 'unsupported-stack-op))))))

# ​​Lexing

Our first step is turning the string we want to evaluate into a list of tokens; breaking up one long string into its constituent pieces.

"18 2   +     4    / "           →           [18, 2, '+', 4, '/']

We could use racket’s lexer package, but that’s a little overkill; we will see that later. For now we can use racket’s string-split function since all of our tokens will be separated by white-space.

Write the procedure lex: string → list.

(lex "18 2 + 4 /") →  '(18 2 "+" 4 "/")

lex should turn numbers in the string into scheme numbers (use the string→number procedure along with nan?).

# ​​Evaluating Postfix

Write the procedure evaluate: list x stack → stack using the post-fix evaluation strategy.

(evaluate (make-stack) (lex "18 2 + 4 /")) →  '(5)