Comp 212 Spring 2001, Project 2: RPN Calculator

Due Monday 9 Apr. 2001 11:59 PM.

For this project, you will write a Reverse Polish Notation (RPN) calculator that evaluates postfix expressions. The calculator will be written in Java and will emphasize a stack-like data structure, Java GUI construction (using the MVC Pattern), and stream I/O.

Overview of RPN (postfix) evaluation

Consider the mathematical expression

(5 + 3) * 2 - 9
This is called infix notation, because the operators are inbetween the operands. Because of precedence, we are sometimes forced to group subexpressions with parentheses. Alternatively, we can write the same calculation, placing the operators after the operands:
5 3 + 2 * 9 -
Note that parentheses are no longer needed; this is always the case. (Another benefit of postfix over infix is that it easily handles operands with more than two arguments. This however won't be important for this project.)

Postfix calculations can be implemented in a very straightforward manner using a stack. As you get an operand, push it on the stack. As you get an operand, pop its arguments, do the operations, and push the result. The first operand of a binary operation is always the lower one on the stack (and the one entered first), so a binary operation is implemented with code like

     second = pop();
     first  = pop();
     push(first - second);

RPN is familiar to many students as how Hewlett-Packard calculators behave.

Roll operations

The calculate will also support two "roll" operations, as found on HP calculators. Rolling it "up" moves the top of the stack to the bottom, thus moving all other values up one place. Rolling it "down" similarly moves the bottom of the stack to the top. Observe that these operations break the strict stack behavior.

Instead of using a stack, you must implement a deque (or doubly-ended queue, pronounced like "deck"). A deque is like a queue, except that it supports enqueues and dequeues at each end. For the sake of convenience and familiarity, we continue to use the word "stack" in this assignment to refer to this deque.

Specifications

The calculator will accept two kinds of input:

For the sake of comparison, you can look at the UNIX programs

The calculator will work with floating point numbers. Use the types double and Double.

The calculator will support the following operations and their keyboard syntax:

You must use the provided IDeque interface. Arrays and CLists are both natural candidates for the underlying data structure.

The calculator will have a GUI interface for entering numbers and the above operations. It will also have a way to swap between expression and immediate mode, without changing the stack contents. In each mode, the irrelevant GUI features should be disabled. In expression mode, the user can type in an expression, load an expression from a text file, save an expression to a text file, or evaluate this expression. For simplicity, you may hard-wire into your program a single text filename for this. The top of stack (if any) is displayed at all times -- note that the top of stack only changes when an expression is evaluated, not while it is entered.

If you wish you may add extra elements to your program, but these won't be graded. E.g., to help you debug, you might want to display the top 2 or more elements of the stack at all times, instead of just the top 1 element.

Milestones

This project is divided into two milestones. In the first milestone, you write the model. In the second milestone, you write the view and control.