Stack Example
Data Structures and Abstractions
Stack Example
Lecture 23
*
A Calculator
It is possible to use two stacks to do simple one line calculations.
The first stack stores operators (characters) that have not yet been performed.
We will start with just + – * /.
The second stack stores the numbers being operated upon.
Therefore we are trying to find the answer to something like
10 + 8 / 2 – 6 * 5
What is the answer to this?
For simplicity’s sake, we will assume integer input, but floating point output.
*
*
Using Diagrams
Try this yourself or in a group.
Draw up an array (set of boxes) to represent the string:
“10 + 8 / 2 – 6 * 5”
With one number (not digit but the whole integer) or operation in each box
Draw an array for the number stack and one for the operation stack
Figure how to do it with diagrams first.
*
*
Test Data
The next thing, of course, is to design the test data: build the test plan.
Construction of the test plan occurs before any code is written.
The test plan is written once you have analysed the problem to be solved
Gets added to as software development progresses.
I came up with over 50 possibilities that should be tested in the test plan!
See the spreadsheet with testdata related to this lecture note.
More extended examples of testing in the “testing 4 later units” folder.
You must perform regression testing. This can be “painful” so think of ways to automate the testing process. You don’t have to use it in this unit but should in later units. Various approaches are used in industry.
Ignore advice about test plans and testing at your own peril.
*
Top Level Algorithm
We are used to the infix notation: 2 + 3 and using this notation means that when you want to override operator precedence, you need to use ( ) as in (2 + 3) * 5.
In Polish (discovered by a Polish logican Jan Lukasiewicz) notation (prefix notation), there is no need to use ( ). Prefix notation: + 2 3
Someone else came along later with something called Reverse Polish Notation (postfix form). Postfix notation: 2 3 +
With RPN, there is an additional advantage in that operators are in the correct order for digital computers.
RPN examples: 2 3 + 5 *
So think this way: push the numbers on the stack until you get an operator. Then pop the last two numbers of the stack and apply the operator. Put the result back on the stack and repeat the whole process. This is easy. The question is how to convert from infix to RPN (postfix). [1]
*
*
[1]
Out of interest, you may want to find out about Dijkstra’s Shunting Yard algorithm.
If you feel that you must go to the original source of this algorithm, see Dijkstra’s paper at https://repository.cwi.nl/noauth/search/fullrecord.php?publnr=9251. Keep in mind that the
paper was written around the time when a number of “computer science” concepts were
being invented, and “Computer Science” was not a fully fledged discipline it is now.
If you prefer to watch a video explaining this problem, you would find a few of various qualities.
If you pay attention in your later units, you will encounter a number of Dijkstra’s other algorithms. A number of these
are listed in the wiki entry for Dijkstra https://en.wikipedia.org/wiki/Edsger_W._Dijkstra.
Top Level Algorithm
Assuming that we have the equation in a string, try to design an algorithm that will do the top level of process control of the string….
Use what you understood when you tried to figure it out using a diagram. If you have forgotten go through using diagrams again.
In other words, most of it will be enclosed in a loop
WHILE more characters
ENDWHILE
Remember to keep it a control function: put off until later working out how things are actually done.
In other words, concentrate on what not how.
Normally (of course), we would be designing, coding and testing in parallel.
*
*
Next…
Next work on each part of the algorithm that you have got, as a what not a how.
Ideally, you should do this with a group of two or three other people. But you can always give it a go on your own.
*
Readings
Textbook: Stacks and Queues, section on Application of Stacks: Postfix Expressions Calculator.
The RPN calculator is described in the above section.
There are a number of calculators which accept RPN entry and therefore make calculations of long expressions easy – less keys to press to get the same result.
*