Assignment 5 – The Stack
Objective
1. Describe and implement a Stack
2. Use a Stack to implement an RPN calculator
Supports Outcomes
1. Describe both complex and simple data structures.
2. Select the correct data structure and algorithm to solve specific problems.
3. Implement data structures and algorithms in computer code.
Lectures
Module 4 – Follow the materials available at Topic – Stacks and Queues. You should have a good understanding of Lists at Topic – Basic Data structures . A List can be a Queue or a Stack. These are simply implementations of a List with specific properties.
Assignment
Implement a Stack in Javascript (you will turn in a link to your program in JSFiddle). Do not use an array as the stack or in the implementation of the stack. Repeat – You MUST implement the Stack (start with your linked list) without using an array. You should start with the List you created in Assignment 4 and simply add the functions Push and Pop. You can do this in JSFiddle by using the Fork ability and giving the new “forked fiddle” a new name.
You will build a Stack Computer from your stack. When a number is entered, it goes onto the top of the stack. When an operation is entered, the previous two numbers are popped from the stack, operated on by the operation, and the result is pushed onto the top of the stack. This is how an RPN calculator.
For example;
2 [enter] 2
5 [enter] 5 2
* [enter] * 5 2 -> collapses to 10
would leave at 10 at the top of the stack.
The program should use a simple input box, either a text field or prompt, and display the contents of the Stack.
Contents of Stack:
For simplicity, the algorithm for the Calculator is;
– Get Entry from the interface
– If the entry is a number – Push to Stack
– If the entry is an operator (+, -, *, /) Pop the last 2 elements off the Stack, Perform the operation on the top 2 elements on the Stack and Push the result onto the Stack.
-Each Push Operation should Display the Contents of the Stack
Information
Building A Stack is relatively easy if you have built a List. Add two extra functions to your List; Push(_value) and Pop(). The Push function obviously needs an argument _value. The Pop function should always return the element on the top of the stack and at the same time remove it from the top of the stack. You may return the Node or the contents of the Node.
This assignment starts you right off with a useful implementation of a Stack – what we call a Stack calculator. It demonstrates the fundamental structure used in calculation within the computer. The Stack Machine is an incredibly efficient and useful computing device and is thoroughly documented in the Wikipedia Article https://en.wikipedia.org/wiki/Stack_machine . This is just the first use you will find for the List.
Assignment Grading – Implementation of a Stack using an array will not be accepted (no grade will be assigned). A stack computer created using a Stack (with correct push and pop) that performs all operations correctly – and does not allow bad entries (non-numeric or operation, no operations until two numbers on the stack) will be worth full credit.
Additional
- The stack computer concept can easily be made into a Tetris-style game. Imagine numbers falling onto multiple Stacks – these numbers pile up unless the user applies an operator to the stack. Operators would operate on the last two numbers performing the operation. When the user gets three common numbers in a single row – they are removed, and the row collapses further.
Question: What kind of structure and algorithm is needed to make a game like this?
- Here is a great video from ComputerPhile (and thanks to Clarence Downs for finding this) that explains infix, postfix, and prefix notation and why this is so important. https://www.youtube.com/watch?v=7ha78yWRDlE