|
// ********************************************************
// Header file stack.h for STACK LinkedList implementation.
// ********************************************************
// #ifndef __STACK_H
// #define __STACK_H
// "typedef" provides easy means to change type of stack
typedef int StackItemType;
class Stack {
private:
struct StackItems {
StackItemType item;
StackItems *below;
} *top;
public:
Stack(); // default constructor
// stack operations:
bool isEmpty();
// Determines whether a stack is empty.
// Precondition: None.
// Postcondition: Returns true if the stack is empty;
// otherwise returns false.
void push(StackItemType& newItem);
// Adds an item to the top of a stack.
// Precondition: newItem is the item to be added.
// Postcondition: If the insertion is successful, newItem
// is on the top of the stack
bool pop();
// Removes the top of a stack.
// Precondition: None.
// Postcondition: If the stack is not empty, the item
// that was added most recently is removed. However, if
// the stack is empty, deletion is impossible.
// Returns false is the stack is already empty.
bool pop(StackItemType& stackTop);
// Retrieves and removes the top of a stack.
// Precondition: None.
// Postcondition: If the stack is not empty, stackTop
// contains the item that was added most recently and the
// item is removed. However, if the stack is empty,
// deletion is impossible and stackTop is unchanged.
// Returns false if the stack is empty.
bool getTop(StackItemType& stackTop);
// Retrieves the top of a stack.
// Precondition: None.
// Postcondition: If the stack is not empty, stackTop
// contains the item that was added most recently.
// However, if the stack is empty, the operation fails
// and stackTop is unchanged. The stack is unchanged.
// Returns false if the stack is empty.
void displayAll();
// Display all values on the stack
// Precondition: None.
// Postcondition: None.
int getLength();
// Determine the number of elements in the stack
// Precondition: None.
// Postcondition: None.
// Returns the number of elements in the stack
void Operation(Stack &s, char op);
void display(stack& myStack);
void getTop(stack& myStack);
void bottom(stack myStack);
void all(stack myStack);
void clear(stack& myStack);
}; // end class Stack
//#endif
// *********************************************************
// Implementation file stack.cpp for
// STACK LinkedList-based implementation.
// *********************************************************
#include "stack.h" // Stack class specification file
//typedef int StackItemType;
Stack::Stack() { top = NULL; } // default constructor
bool Stack::isEmpty() {
return top == NULL;
} // end isEmpty
void Stack::push(StackItemType& itemIn) {
StackItems *newItem = new StackItems(); // create new node
newItem->item = itemIn; // load values
newItem->below = top;
top = newItem; // make top point to this new item
} // end push
bool Stack::pop() {
if (isEmpty()) return false;
// temporarily save current top pointer location so it can
// be later deleted (dynamic memory freed)
StackItems *tempTop = top;
top = top->below; // move top to one below it
delete tempTop; // free space allocated to old top
return true;
} // end pop
bool Stack::pop(StackItemType& stackTop) {
if (isEmpty()) return false;
// stack is not empty; retrieve top
stackTop = top->item;
pop();
return true;
} // end pop
bool Stack::getTop(StackItemType& stackTop) {
if (isEmpty()) return false;
// stack is not empty; retrieve top
stackTop = top->item;
return true;
} // end getTop
void Stack::displayAll() {
if (isEmpty()) cout << "Stack is empty." << endl;
StackItems *temp = top;
while (temp != NULL) {
cout << temp->item << endl;
temp = temp->below;
}
} // end displayAll
int Stack::getLength() {
StackItems *temp = top;
int count = 0;
while (temp != NULL) {
count++;
temp = temp->below;
}
return count;
} // end getLength
void Operation(Stack &s, char op)
{
int product, difference,sum,num1, num2;
float quotient, remainder;
switch(op)
{
case '+':
s.pop(num1);
s.pop(num2);
sum= num1+num2;
s.push(sum);
break;
case '-':
s.pop(num1);
s.pop(num2);
difference= num2-num2;
s.push(difference);
break;
case '*':
s.pop(num1);
s.pop(num2);
product= num1*num2;
s.push(product);
break;
case '/':
s.pop(num1);
s.pop(num2);
quotient= num2/num1;
s.push(quotient);
break;
case '%':
s.pop(num1);
s.pop(num2);
remainder= num2/num1;
s.push(remainder);
break;
case '=':
s.pop(num1);
s.pop(num2);
if(num1==num2)
s.push(1);
// return 1;
else if (num1!=num2)
s.push(0);
// return 0;
break;
}
}
void display(stack& myStack)
{
cout<< myStack.top();
myStack.pop();
}
void getTOP () {
cout<< myStack.top();
}
Void bottom (stack myStack) {
for(int i=1; i<myStack.size(); i++)
{
myStack.pop();
}
cout<<myStack.top();
}
void all(stack myStack){
while(myStack.size()>0)
{
myStack.pop();
}
}
Void CLEAR(Stack &s) {
s.pop(AllStackItems);
}
// ***********************************************************
// Main Test Module for STACK LinkedList-based implementation.
// ***********************************************************
#include <iostream>
#include <stdio.h>
#include "stack.h"
using namespace std;
typedef int StackItemType;
int main (void) {
cout <<"Shannon Wilson sjw0100@unt.edu"<< endl
<< "CSE 2050, Program 3 << endl << endl;
//display initial program identification
Stack test;
StackItemType num;
char * pch;
char str[80],str1[80];
strcpy (str,"\0");
while(cin >> str1){
strcat(str,str1);
strcat(str," ");
}
pch = strtok (str," ");
while (pch != NULL)
{
printf ("%s\n",pch);
pch = strtok (NULL, " ");
}
// test.push(num);
// test.push(23);
// test.push(-4);
//test.push(101);
// }
if (!test.getTop(num)) cout << "Nothing on top to get." << endl;
else cout << "The top item is " << num << endl;
while (!test.isEmpty()) {
if (test.pop(num)) cout << num << endl;
else cout << "Error: Nothing to pop." << endl;
}
if (!test.pop(num))
cout << "Nothing to pop." << endl;
for (int i=1; i <= 10; ++i)
test.push(i);
test.displayAll();
cout << "The length is " << test.getLength() << endl;
return 0;
} // main
|
1 Jul, 2008 - 08:15 PM
| 