LAB 4

Due Tuesday, February 9, 9PM

Reverse-Polish Calculator

Graded assignment; all work must be strictly your own.  Do not show or
describe your program to other students.  On this assignment, you may
discuss programming issues along the lines of "I don't know how
procedures work" answered with examples unrelated to this assignment.
You can use the text (or talk to myself or a TA) if you do not
understand base conversion.

This is the last assignment in the series of base conversion, number
use I/O, and adding machines.  As such, it will have a weight of 15
(rather than 10), so if your base conversion program wasn't quite all
there, here's your chance to get some of that back.

Reverse-polish notation can be used for stack-based expression
evaluation.  Its primary advantage is its minimal approach to
non-operand keystrokes (that is, there are no parentheses or equal
sign keys to press).  The notation is used by HP calculators (the
only *real* brand of calculator).

It is a postfix notation, meaning that operands preceed operators, as
in:

1
2
+

which would print out 3.  The 1 and the 2 are implicit pushes onto a
stack, and the + is a pop-2-push-1 operator, so we could continue with

1
2
+
4
*

to get 12.  A parenthesised expression is evaluated inside out, so
(3*(4 + 5*(6+1))) becomes either of the following, where the second
makes ample use of the stack by pushing all the operands first (in the
correct order) and then operating on them.

6     3
1     4
+     5
5     6
*     1
4     +     #  6+1
+     *     #  *5
3     +     #  +4
*     *     #  *3


The program will take inputs terminated with newlines (if you would
like, and you are using a version of spim with unbuffered I/O, you can
process single-character operators without a newline, print out the
newline rather than requiring the user to type it).

Inputs are:
  Unsigned numbers in arbitrary base comma format
Operators:
  Pop 2 and push result operators:
    +, -, *, / (integer division), % (integer mod)
  Pop 1 and push result operator:
    !  (change sign, or negate)
  Pop 1 operator
    #   change base  (with the base being the top element of the
        stack)
  Other operators:
    x   quit program
    c   clear stack 
    p   print stack


Note: If you allow very high radix (base), for example, base 65536,
every 16-bit unsigned number will be represented without commas in
base 10!

Additional features (not required)
   a.  Include additional operators (bitwise, square root, etc)
   b.  For bases <= 16, do I/O without the commas
   c.  Check for overflow
   d.  Nice error messages (you *must* have error messages for
       underflow and overflow)
   e.  Add other stack functions and explain why they are useful 
       in your README.  For example, duplicate top of stack, rotate
       stack, copy n'th element down to top of stack.
   f.  Read about Sun's picoJava stack machine.

===========================================================
HANDIN:

stack.spim
README
    a.  Name and email address
    b.  Overview of your code
    c.  Discussion of any additional features

Points:  15 points maximum

	 Basic functional program:  10 points

	 Checkoff:
	   -1     Late Checkoff (Wednesday; no latter)
           -1	  Not quite fully functional
	   -2     Not entirely functional
	   -3     Almost entirely not functional
	   -4     No checkoff
	   +1/2   Exceptionally well organized demo with neat
	   	  features. 
           +1/2   Checkoff on Monday

	 Comments:
	   -5     None
	   -1..-2 Poor
           +1/2   Excellent comments and README

	 User interface:
	   -1   None
           +1   Excellent prompts and user interface

	 Error messages:
	   +1   Excellent error messages 

	 Extra stuff:
	   +1..+4
           -3  Uses only base 10, native SAL I/O

	 Coding:
	   +1/2   Incredible code 
	   -1..-3 Confusing control structures, variables, and the like.

	 Procedures
	   -5     No procedures 
	   -1..-2 Poorly structured procedures