Project 4: RPN Calculator

The goal of this project is to practice using stacks in an algorithm.

1. Introduction

Polish mathematician Jan Lukasiewicz invented a notation for arithmetic where the operator comes before the operands, for example + 5 3 instead of 5 + 3. The advantage of this is that the order of operation is always unambiguous without the need for parentheses (or even precedence rules). For example, 5 * 3 - 9 is written - * 5 3 9, whereas 5 * (3 - 9) is written * 5 - 3 9. In honor of its inventor (or his nationality, at any rate), this is referred to as Polish notation. (It is also called prefix notation, in contrast to normal arithmetic notation which is thus infix.)

Reverse Polish notation is similar except that the operator is put after the operands (so it is also postfix notation). The advantage is that all the operands are then known before the operator is read, if we read the string from left to right. This notation is particularly interesting for our purposes, because a stack can be used to evaluate expressions in RPN. Your task is to write a calculator that evaluates expressions entered in RPN.

2. Setup

In this project you will use the same GUI as in the earlier calculator example. So to get started, you'll need to clone the starting repository for that project (project2) into a new directory:

hg clone /cslab/class/csci245/project2 project4
That will give you a new direcgtory project4, with the code in the package (subdirectory) calc.

3. Calculator details

One difficulty in using RPN, especially on a simulated hand-held calculator, is how to delimit the operands. The string 937+ could mean 9 + 37 or 93 + 7. In a string, this disambiguation would be done using spaces. For your calculator, you should interpret the "." button as indicating the boundary between numbers. Consequently, your calculator needs to work only on integers; division should be integer division. This also means that you don't have to worry about screen overflow or other formatting. I also won't be checking for how you handle division by zero. Additionally, the equals button is useless—you do not need to do anything when it is pressed.

Generally this is an easier project than the previous calculator project (and easier than the next calculator project...). The emphasis is not on polishing (heh heh) the calculator's extreme cases but on using the stack.

Even though this section of the course is about data structures, you should keep thinking about object-oriented design. You've heard that in the future you will be given a project where you have to write a calculator without any ifs. I highly recommend you do a practice run on that this time. See if you can avoid using any if statements this time aroun—-or at least as few as possible, and isolate any you need.

You should also implement the clear button. This should reset the entire calculator. Moreover, if the user presses the operation buttons when there is not enough information in the stack, your calculator should just ignore it. You calculator should not crash in such a situation.

4. To turn in

Be sure that you have committed all of your updates to the Mercurial repository. Then, from your project4 directory, do

/cslab/class/csci245/bin/handin project4 .hg calc/*.java

DUE: Monday, April 15, 2013, at 5:00 pm.


Thomas VanDrunen, Cary Gray
Last modified: Wed Apr 10 15:33:55 CDT 2013