Problem Set 2: A graphical RPN Calculator
[Due 2/3 at 11:59pm]

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.

Administrative

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

Turn in your solution by email. Please send all source, project and solution files needed to compile your project to Peter-Michael. Don't forget to include a file with your written answer to part 1. You submission should be in a single zip file (see the policy page for more information).

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 your 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> <spaces> <token> <spaces> <token> ... and the sequence of tokens represents a RPN expression that evaluates to a number. Each <spaces> is a string of one or more spaces. 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 left of operators (i.e. left of +, -, *, or /). 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 (because 1.0 2.3 + is valid)
xinvalid
1 +invalid
11 + invalid (even though 1 1 + is valid)
1 2 -3 + invalid (even though 1 2 - 3 + is valid)

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

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.

Challenge Problem: Calculator Extensions

Work on this optional challenge problem only after you have completed the rest of this problem set.

Modify your gui so the calculator can be operated in either a strict or extended mode. When in strict mode, the calculator should meet the part 2 specification. When in extended mode, the calculator may accept expressions defined as invalid in part 2.

Add one or more of the following features to your calculator's extended mode.

If you work on the challenge problem, submit a text or pdf file describing your extended mode.