### 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.

#### Administrative

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 |

`x` | invalid |

`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.