07.STACKS

SYNTAX

DEFINITIONS

STACK

• a list of homogenous elements, wherein the addition & deletion of elements occurs only at one end (top of the stack).

• The stack is a last-in-first out concept (LIFO) or first-in-last-out (FILO) data structure

  • the bottom element of the stack is the earliest/first added one - this is the last one to be deleted

  • the top element is the last added item

    • the last added item will be the first one to be deleted

STACK BASIC OPERATIONS

• isEmptyStack: Checks whether the stack is empty

• isFullStack: Checks whether the stack is full

  • this can only be done if the implementation is an array list

• push: Adds a new element to the top of the stack

• top: Returns ore retrieves the information from top of the stack

• pop: Removes the top of the stack

STACK IMPLEMENTATION METHODS

• Update the ArrayList class to define the three main stack functions: push, top, & pop

• Update the LinkedList class to define the three main stack functions: push, top & pop

• Define a new class Stack that inherits the class ArrayList

• Define a new class Stack that inherits the class LinkedList

STACK PRACTICAL APPLICATION: HANDLING INFIX ARITHMETIC EXPRESSION

STACK PRACTICAL APPLICATION: HANDLING POSTFIX/PREFIX NOTATION IN ARITHMETIC EXPRESSION

postfix expression simplifies the manipulation of arithmetic expression

TRANSFORMING INFIX EXPRESSIONS TO EQUIVALENT POSTFIX EXPRESSION

STACK APPLICATION (POSTFIX)

PROCEDURE

1. push(6)

2. push(3)

3. whenever an operator is encountered, the last two pushed elements (6,3) in this case must be handled using the plus sign

4. x = top()

   1. x will be 3

5. pop()

   1. this removes 3 from the stack

6. y = top()

   1. y will be 6

7. pop()

   1. this removes 6 from the stack

8. push(x +y)

   1. the stack will now have 9 which is the sum of 6 and 3

9. push(2)

10. m = top()

    1. m will be 2

11. pop()

    1. this removes 2 from the stack

12. n = top()

    1. n will be 9

13. pop()

    1. this removes 9 from the stack

14. push(m * n)

    1. the stack will now have 18 which is the product of 9 and 2

ALGORITHM

IMPLEMENTATION

UML

VISUALIZATION

SOURCE CODE

HEADER FILE: arrayList.h

/*################################################
# Name: Stephen Razon
# Student ID:
# Date: 111003NOV24
# Filename: arrayList.h
# Dependency: N/A
################################################*/

template <class Type>
class ArrayList
{
protected:
	int selfLength, selfMaxSize;
	Type* selfList;
public:
	ArrayList(int);              //constructor
	bool isEmpty();
	bool isFull();
	int listSize();
	int maxListSize();
	const void print();
	bool isItemAtEqual(int, const Type&);
	void insertAt(int, const Type&);
	void insertEnd(const Type&);
	void removeAt(int);
	void retrieveAt(int, Type&);
	void replaceAt(int, const Type&);
	void clearList();
	int seqSearch(const Type&);
	void insert(const Type&);    //without duplication
	void remove(const Type&);
	ArrayList(const ArrayList<Type>&);     //copy constructor
	~ArrayList();
	const ArrayList<Type>& operator=(const ArrayList<Type>&);
};

HEADER FILE: stack.h

#include "arrayList.h"

template<class Type>
class Stack : public ArrayList<Type>
{
  public:
    Stack(int);
    bool isEmpty();
    bool isFullStack();
    void printStack();
    void push(const Type& x);
    Type top();
    void pop();
};

template<class Type>
Stack<Type>::Stack(int maxSize) : ArrayList<Type>(maxSize){
  //we call the constructor of the ArrayList with a parameter maxSize
  //the maxSize in ArrayList<Type>(maxSize) will be the maximum number
  //hence, there is no statement necessary in this section
}

template<class Type>
bool Stack<Type>::isEmpty(){
  return ArrayList<Type>::isEmpty();
}

template<class Type>
bool Stack<Type>::isFullStack(){
  return ArrayList<Type>::isFull();
}

template<class Type>
bool Stack<Type>::printStack();{
  ArrayList<Type>::print();
}

template<class Type>
void Stack<Type>::push(const Type& x){
  ArrayList<Type>::insertEnd(x);
}

template<class Type>
Type Stack<Type>::top(){
  int n;
  Type x;
  n = ArrayList<Type>::listSize();
  //the position at n-1 will be stored in x
  ArrayList<Type>::retrieveAt(n-1, x);
  return x;
}

template<class Type>
void Stack<Type>::pop(){
  int n;
  n = ArrayList<Type>::listSize();
  ArrayList<Type>::removeAt(n - 1);
}

#include<iostream>
using namespace std;
#include"Stack.h"
#include<string>
#include<iomanip>

template<class Type>
void postfix(Stack<Type> s)
{
	string e;
	float num, num1, num2;
	cin >> e;
	while (e != "=") 
	{
		if (e == "+")
		{
			num1 = s.top();
			s.pop();
			num2 = s.top();
			s.pop();
			s.push(num1 + num2);
		}
		else if(e == "-")
		{
			num1 = s.top();
			s.pop();
			num2 = s.top();
			s.pop();
			s.push(num2 - num1);
		}
		else if (e == "*")
		{	
			num1 = s.top();
			s.pop();
			num2 = s.top();
			s.pop();
			s.push(num1* num2);
		}
		else if (e == "/")
		{	
			num1 = s.top();
			s.pop();
			num2 = s.top();
			s.pop();
			s.push(num2 / num1);
		}
		else
		{
			num = stof(e);
			s.push(num);
		}
		cin >> e;
	}
	cout << setprecision(2) << fixed << s.top() << endl;
}

int main()
{
	/*Stack<int> s(10);
	cout<<"Is empty stack? "<<s.isEmptyStack() << endl;
	s.push(10); s.push(2); s.push(25);
	cout << "Top = "<<s.top() << endl;
	s.printStack();
	s.pop();
	cout << "Top = " << s.top() << endl;
	s.printStack();
	cout << "Is full stack? " << s.isFullStack() << endl;*/

	//code for postfix evaluation
	Stack<float> s(10);
	postfix(s);
	return 0;
}