Problem Set 2: A graphical RPN Calculator
[Due 2/6 at 10am]

In this assignment you will implement a simple graphical calculator for evaluating arithmetic expressions in Reverse Polish Notation (RPN). The program will have a history function for recalling old calculations.


Work on this project with a partner. Please send me mail by Friday, January 25 if you would like to work with someone in particular. I will pair up everyone else.

Turn in your solution by email. Please send me all source, project and solution files needed to compile your project. Don't forget to include a file with your written answer to part 1.

Reverse Polish Notation

Normal, or infix, mathematical notation requires parentheses to write certain expressions. For instance, when we write (3 + 9) * 9 parentheses are needed to force the addition to happen before the multiplication. RPN, or postfix notation, is a technique for writing expressions without need for parentheses. Instead, subexpressions are grouped by position. In RPN we build an expression by writing an operator's arguments followed by the operator itself. So 3 + 9 is written 3 9 +, and (3 + 9) * 9 is written as 3 9 + 9 *. Likewise 2 * (7 - 4) is written 2 7 4 - *.

Part 1: The RPN Evaluation Algorithm

Evaluating infix expressions is hard, but there is a simple, stack-based algorithm for evaluating RPN expressions. Write this algorithm in pseudo code, and provide a short argument explaining why it is correct. Turn in you solution as a pdf or plain text file.

You may consult Google or a printed source (e.g. Data Structures and Problem Solving using Java by Weiss) for the algorithm. However, the correctness argument must be your own.

Part 2: Implementing the Evaluator with History

Time to put the theory to use. Write a class that implements the ICalcSession interface provided here. This interface contains three methods.

The Eval method calculates RPN expressions given as strings. However not all strings are good RPN expressions. You only need to evaluate valid strings; on all others you may return a string containing "Error".

An string is defined to be valid when it has form <token> <space> <token> <space> <token> ... and the sequence of tokens represents a RPN expression that evaluates to a number. Each <token> is one of +, -, *, /, or a number. A number is any string for which double.TryParse returns true. A string is semi-valid when it can be made valid by inserting spaces next to operators. A string is invalid when it is neither valid nor semi-valid. For example:

3 4 + 2 7 * -  valid
-2.3 3.0 *valid
1.0 2.3+semi-valid
1 +invalid
11 +invalid

The remaining two methods, HistoryBack and HistoryForward provide a way to browse past inputs to Eval. Their behavior is documented in ICalcSession.cs.

Provide NUnit tests for your code.

Part 3: Add a Graphical Interface

Design a gui to expose all calculator functionality. From the gui it must be possible to enter any valid string, navigate the history, and evaluate expressions.