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.