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 as a Queue and a Stack are simply implementation of a List with specific properties.

In All Course Lectures - Lecture 2.3 (Queues) and Lecture 2.4 (Stacks) will introduce you to the concept of a Stack and start you on the path of implementing a Stack in Javascript code. Note that the Stack computer is a classic example of programming.

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 the use of an array..

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 2 numbers are 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:

Information

Building A Stack is relatively easy if you have built a List. A Stack is nothing more complex with 2 extra functions added 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 removing it from the top of the stack.

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 at 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 2 numbers on 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 2 numbers performing the operation. When the user gets 3 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?

All COP3530 Assignments