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 .
The magic of postfix is that it is relatively easy to evaluate expressions using a single stack; very little parsing or parentheses. , , and all use postfix notation, and the Java virtual machine is stack-based. Try it out on .
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 .
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.
(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))))))
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 , but that’s a little overkill; we will see that . For now we can use racket’s 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 procedure along with ).
Write the procedure evaluate: list x stack → stack using the post-fix evaluation strategy.
(evaluate (make-stack) (lex "18 2 + 4 /")) → '(5)
Your Forth interpreter should support: