Introduction
This is the first and theoretical part of the series of tutorials to develope a calculator. In this series I want to write a fully working calculator application in C++. It's planned to support different numeric systems, brackets and functions available on scientific calculators.
Let's start.
Last year in a sleepless night I asked my self, how is a calculator working? At this time I was developing a small stack based script engine for my Jump’n’Run framework. After finishing it, I thought about if a calculator could be done with a stack. Next day I searched the web to figure out how a calculator is working in general, but I didn’t find any good explanation(Actually till today I don't know if my way is the common way, or if there is something much better or easier). So, I decided to give it a try. Without knowing anything about it, I simply started by analysing the behaviour of my calculator.
The Problem
The question that I was interested in most, was what are the rules for the calculation of a term, if you don't know the whole term. Let me show you this problem:
We will calculate this term:
6*3+2*2+(2+3)
To calculate this term you may use this way:
0: 6*3+2*2+(2+3)
1: 18+2*2+(2+3)
2: 18+4+(2+3)
3: 18+4+5
4: 27
One reason why you can do this, is you know the whole term from the beginning on. You are in a better situation than a calculator with this term typed in. At time n the calculator just knows all positions of the term less or equal than n. Although without knowing the whole term it's starting to calculate. How does this work? That's the point my question was about.
Analysis
I started to analyse the behaviour of my calculator(TI-30Xa) and figured out some points:
At this point we just care about these operations +, -, *, /, (, ).
- While entering a number the displayed number doesn't really behave like a number. It's more a string than a number.
- Pressing number keys never causes any calculation.
- Pressing operator keys sometimes causes calculation.
- Calculation may happen after every operator.
Now let's take a closer look at these points.
STRUMBER - STRing/nUMBER
When we start to enter a number the displayed number behaves like a string. Let's try to enter 1024 on a calculator. We start pressing #1, #0, #2 and #5. What happened here? These numbers got concatenated. Hm, I think we mistyped a number. The display shows 1025 instead of 1024. No problem, we use the back key and the display shows 102. The digit 5 is cut off. Now press #4 and we see 1024.
I think you see what I means by "behaving like a string".
The point is as long as the display number isn't used in a calculation it's a string.
Pressing number keys never causes any calculation
There is nothing to say, try it. You can enter any number you want, the calculator will never calculates anything.
Pressing one of the operator keys sometimes causes calculation.
Write down some terms and enter them in your calculator. Whenever you see any calculation note a "|" at the corresponding position in your notes.
Examples:
6*2+|3+|4*2=|
1024/2*|(2+2)|-|1+|2=|
7+2*4*|0,5=|
What do we see?
#( never causes a calculation. At the moment, we don't know what this key actually does.
Whenever a calculation was done, one of the following keys was pressed: #+ #- #* #/ #) #=
From this point of view we will call them all operators. Sorry for that impreciseness, because #( and #) aren’t operators from the mathematical point of view.
At the moment we don't see any rules what operator in what position causes a calculation. It's more complicated than to say whenever #* is pressed do calculation. Take a look at the first term "...4*2=", here it doesn't cause a calculation and in the last term "7+2*4*" the last one does. But till now we have the following rules:
- If one of the following keys are pressed #0 #1 #2 #3 #4 #5 #6 #7 #8 #9 #- or #, manipulate the display number.
- If one of the following keys are pressed #+ #- #* #/ or #) try to calculate.
Calculation system
I developed this system by trial and error. I started with the simple idea to push the numbers and the operators on their stacks and try to calculate the term. If I saw the system failing, I figured out the point why it’s not working and changed it. After a while and some cups of tea it got better and better. And finally it worked.
Here it is:
First, each operator gets a priority:
/ * 3
- 2
+ 1
Next we need two stacks, one to store the numbers and one to store the operators.
Additionally we need a variable to store the priority of the operator we entered last(Let's call it pol).
And finally a term to calculate: 6+2*3-(2+3)=
To calculate the term we have to use these tools in combination with the following rules.
1. If a number key is pressed, manipulate the display number in a corresponding way.
- If a operator is pressed, do the following:
1. Push the display number on number stack.
2. Try a calculation
3. Push the pressed operator on the operator stack.*
4. set pol to the priority of the pressed operator.
- If #( is pressed
1. set pol to 0.
2. set display number to 0.
3. Push the pressed operator on the operator stack.*
- If #) is pressed.
1. try calculation.
2. If the top most operator on operator stack is "(", remove it.*
*) Don't forget #( and #) are operators too.
Try a calculation
This is the most interesting point of the whole system. The calculation itself is quite simple, it works with the following rules:
1. Take the two top most numbers from the number stack.
2. Take the top most operator from the operator stack.
3. Make the calculation and push the result on the number stack.
The source code could look like this:
var op:String = _opstack.pop().toString();
var p2:Number = Number(_numberStack.pop());
var p1:Number = Number(_numberStack.pop());
switch(op) {
case "/":
_numberStack.push( p1 / p2 );
break;
case "*":
_numberStack.push( p1 * p2 );
break;
case "-":
_numberStack.push( p1 - p2 );
break;
case "+":
_numberStack.push( p1 + p2 );
break;
}
Take a look on p1 and p2. P2 is taken first because it's the second number entered and it’s the top most number on the stack now. And we know 10-2 != 2-10.
Do you thing we have got everything needed? No, there is one last point. If we do a calculation, we don't have to do one calculation, we have to do as many calculations as possible. This is the point where we pay attention on pol. We start the calculation if the priority of the currently pressed operator is less or equal than the priority of the topmost operator on the operator stack and repeat the calculation as long as pol(priority of the last entered operator) is higher or equal as the priority of the top most operator on the operator stack.
The source code could look like this:
while (
getPriority( nop ) <= getPriority(_opstack[_opstack.length - 1])
&& _pol >= getPriority(_opstack[_opstack.length - 1])
&& _opstack[_opstack.length - 1] != "("
) {
... calculation
}
That's it! This is the very basic system of the calculator.
Of course there is much more to say, for example:
- This is working if we enter a term with a correct syntax. But what about this one:
3*2+((2-3)+4=
- If the result of a calculation is shows, we can’t manipulate it by pressing a number key or comma key.
Points of Interest
Probably you may want to know why I wrote this article. Last year I have written a calculator in Actionscript in Flash. But currently I am learning C++ and wxWidgets and for that, I needed a small project to realize. And that's the reason why I rewrite this calculator.
On top of that, I thought it could be interesting to other people to see how it works and so, I wrote this article.
If you know a different system to make a calculator working, please let me know.
History
2008-10-15
I have got some poor ratings. I read the article and recognized that I formed the main question in a wrong way. (Can a calculator be done by using stacks). And I didn't point out what I am going to do in this series. Content didn't change much, but hopefully it's better now.
2008-10-12
First release.
