Curriculum Simple RPN Calculator
From Real Software Documentation
Aim
We’ve done all the hard material in this course now; next, we look at some examples. We’re going to build a simple Reverse Polish Notation (RPN) calculator. If you’ve ever used a Hewlett-Packard scientific calculator, you’ve used RPN. As well as being good practice, this project will get you to think about implementing and using a stack data structure. We also introduce the Model-View-Controller software design paradigm.
Contents |
Model-View-Controller
Much of this course has been designed to get you over the gap between knowing what the individual objects and language features in Real Studio do, and how to put these together into sophisticated programs.
In this project, we will move on from the closer level we’ve looked at so far, to looking at one larger way of structuring an entire program: the Model-View-Controller paradigm (MVC).
Before we look at MVC in more detail, we should consider another theme that has arisen throughout this course: efficiency. MVC will be overkill for many programs.
Remember what we’ve said: in many situations, you should be writing quick, simple, “bad” programs that just solve a problem quickly.
But if you are designing a more significant program, MVC is likely to be a useful way to structure it. If you are designing a program that is somewhere in between, you can also employ a kind of part-way MVC structure.
On to the details. MVC is a very generalized concept, applicable to almost any kind of program. It says that your program should be divided up into objects assuming three quite separate roles:
- Objects in the Model constitute the data your program is designed to manipulate. In a word processing program, this would be the text and its style, along with other formatting information that specifies the content of the document. In a computer game, this might be the ”game world” location (in that world) and current actions of every “actor” in the game, the player’s score, and so on;
- A View is a class or collection of classes that present the model to the user on the screen; and
- A Controller is a class or collection of classes that can manipulate the Model.
By separating these three roles, we gain the ability to vary any of them with minimal changes to the others. For example, assume we built a word processing program using MVC. Now assume we want to make the program into a multi-user program that lets two or more users work on the same document via the Internet. Almost the only change needed should be to write a new set of controller classes. The model and the view will be almost entirely unchanged.
One very important point: a single class can take on roles in two or even all three of the parts of the MVC paradigm. As we will see, Interfaces let us separate the roles within the one object. This will make splitting these roles into distinct objects later on fairly easy, should it become necessary.
The Stack Data Structure
A stack is a data structure with, at minimum, the following operations:
- Push, which takes a single argument;
- Pop, a function which returns a single result of the same type as the argument to Push; and
- Empty, a function which returns a Boolean.
These operations on a stack work in a fashion equivalent to a stack of plates in a cafeteria. Things come off the stack in the opposite order you put them on. In situations where you can’t control the stack from a programming language, or sometimes even then, you might want to have more operations on the stack.
Some of the other common operations you might have are:
- Drop, which removes the top item from the stack;
- Duplicate, which adds an extra copy of whatever’s on top of the stack to the top of the stack;
- Over, which pushes a copy of the next-to-the-top item onto the top of the stack;
- Swap, which switches the top and second from the top items on the stack;
- Size, which returns the count of items on the stack; and
- Clear, which empties the stack.
Reverse Polish Notation
We’ve seen before that any mathematical expression can be represented as a syntax tree. And we’ve seen how a recursive process (which uses a stack) helps us to traverse such a tree.
Put these two observations together, and you get Reverse Polish Notation (RPN). In RPN, operations are written after their operands, rather than between them. An operand is like the argument to a function: it is the information you need to carry out an operation. In the expression:
+ is the operation, and 2 and 3 are the operands.
To interpret an RPN expression, just read it from left to right; numbers are pushed onto a stack, while operations pull their arguments from the stack and then push their results back onto it. Notice how simple this evaluation rule is, compared to the rules for normal arithmetic expressions. There are no precedence rules requiring you to jump back and forth in the expression to evaluate it, and no need for parentheses.
One quick note: we talk about the stack like the plates in the cafeteria: the first things pushed are on the bottom, the last on the top, for example. But the convention in the computer industry is to illustrate a stack on paper as a list, starting with the bottom of the stack at the top of the page. This is just something you have to get used to.
Some examples of expressions in regular and RPN notation:
| Regular Notation | RPN |
|---|---|
| 2+3 | 2 3 + |
| (2+3)*4 | 2 3 + 4 * |
| 2+3*4 | 2 3 4 * + |
Remember, in the expression 2+3*4, because of the conventions of arithmetic, we carry out the multiplication first, so the result is 14. Notice that the RPN version of this expression has the * before the +, reflecting the order in which we carry out the calculations.
Let’s look at how we evaluate the last two expressions. First, 2 3 + 4 *:
| Expression Evaluation Sequence | Stack |
|---|---|
| 2 3 | 2
3 |
| + | 5 |
| 4 | 5
4 |
| * | 20 |
Now, 2 3 4 * +:
| Expression Evaluation Sequence | Stack |
|---|---|
| 2 3 4 | 2
3 |
| * | 2
12 |
| + | 14 |
The Project
Open the included SimpleRPNCalculator project. Run it, and try making some calculations with it.
The Classes and Interfaces
The items in the program have been grouped roughly according to their role in the MVC paradigm.
The StackDisplay Class and the Stack Interface
Notice first that we only have one View class: the StackDisplay class. But this class supports an interface, Stack, which forms part of the Model.
The Stack interface defines the kind of stack operations we have discussed.
The StackEntry Interface
The other Model interface we have defined is StackEntry. This interface was created so we can treat the enter box as part of the stack. If the user has typed in a number but not pressed Enter, we nevertheless want to treat what is entered as the top item on the stack. The methods in this interface let the stack check whether there is something in the entry box, and to enter it if there is something there. The stack can thereby take care of treating this other object as part of itself, so the other parts of the application don’t need to be concerned with it.
We use an interface for this so that the stack object doesn’t need to be hard-wired into a particular entry object. The stack doesn’t need to know anything about what the entry object is; just that it supports the operations in the StackEntry interface.
The StackOperationButton Class
The StackOperationButton class is an abstract class, just adding support for the StackOperation interface to the standard BevelButton (which we’re using like a standard button; it just looks more like a calculator button than a regular button does).
The StackOperation Interface
The StackOperation Interface just defines an object that knows how to manipulate the stack. And that just means it can store a reference to a Stack object when asked to.
The NumEdit Class
We stole the NumEdit class from an earlier project. Code reuse!
The StackEntryBox class
This adds the StackOperation and the StackEntry interfaces to the NumEdit class.
Notice how to declare multiple interfaces for a single class.
The CalcWindow
Object Event Handlers in a Window
In this project, we’ve done something we’ve not done much before: we’ve put substantial amounts of code in the event handlers for the objects in the window.
You should only do this with code that is specific to the operation of the window, or which you are absolutely certain won’t be needed outside the window.
In this project, we needed a whole variety of individual buttons, each with different behavior. We’ve put as much of that behavior as is reasonable in a shared class definition, and the rest in the code for the event handlers for each button in the window.
Notice that each time we add code to the event handler of an object in a window, we are effectively creating a new, unnamed subclass of the object’s class.
The Open Event Handler in the CalcWindow
The Open Event Handler in the CalcWindow does something we’ve not done before: it uses the IsA operator, to specifically test the type of each object in the window.
You should be wary of any occasion in which you are tempted to use the IsA operator. You should always ask yourself if polymorphism could be made to do the job instead.
In this case, in fact, it could; every object in the window could support the StackOperation interface, and objects which aren’t StackOperation objects in the current design could just have empty methods for the StackOperations.
But this would mean adding an extra interface to the StackDisplay class that didn’t belong there, and that would confuse the self-documentation of the design. It would also add complexity with little gain. The initialization code in the window keeps this stuff in one place, and is really pretty simple to understand and maintain. We did think about this design before accepting it, though.
By the way, this situation, in which you have some kind of collection, and you need to do something to a certain type of object within it, is a classic “no right answer” situation in object-oriented programming. Using IsA to find the objects you want is often (thought not always!) a good solution in this situation.
Further Exercises
This is a great project for extension:
- Add more buttons, for more scientific or business functions.
- Add keyboard shortcuts. Rather than requiring them to be set up in a centralized place, the keys in the window should be able to register their own keyboard shortcuts. This allows us to retain an important feature of the program right now: a new key can be added, without adding code anywhere but in the key itself. AsyncKeyDown (look it up in the documentation) is one way to intercept keystrokes. An interesting design question is how much of this feature you can put in the class definition. Another interesting issue is how to handle two or more buttons requesting the same keyboard shortcuts — there is no single, obvious way to resolve this.
- Add keyboard modifiers. I should be able to get Sin-1 by holding down the Shift key and clicking the Sin button. Again, I should be able to write the code specific to each “shifted” operation in the buttons themselves.
- A good test of your understanding of the MVC paradigm would be to separate the stack from the display. This is to say that the stack should be a separate property of the window, separate from its display. There are many ways to handle the user interface and its display in this situation: the stack could just issue a Changed call to the display, and the display could then ask the stack for its content; or the stack could notify the display of every event that happens to it. An interesting option is to have the buttons notify the display when they have finished an operation, and to have the stack notify the display at that point (this would be the most efficient, but would be the hardest to write; our discussions of broad efficiency issues should tell you that “efficient code” is not needed here — but this would be an interesting coding exercise).
