Hi, We have studied stack implementation using ADT of linked lists, and also the

Question

Hi, We have studied stack implementation using ADT of linked lists, and also the pointer based implementation of stack operations(PREFERRED)...

QUESTION :

Use a stack ADT similar to undo button, where each word can be typed in as long as words are not the undo or exit sequence.

The undo sequence can be /uN where /u specifies undo operation, followed by N, number of previous words to undo. The exit sequence can be /x.Assume only one word is entered at a time.

[Hint: Consider a stack of strings]


Eg:
Enter word:I
Enter word:want
Enter word:love
Enter word:u1
Enter word:icecream
Enter word:x
Output: I want icecream.

If number of words to be undo are more than that present in stack, error should be printed.

//////////////////////
I HAVE WITH ME THE FOLLOWING STACK OPERATIONS IN SIMPLE POINTER BASED IMPLEMENTATION,

bool StackisEmpty();
void push(stackItemType Item, bool & Success);
void pop(bool & Success);
void pop(StackItemType & StackTop, bool & Success);
void GetStackTop(stackItemType & StackTop, bool & Success);


////////////////////////OR

I have with me the following functions in linked list ADT

bool ListIsEmpty();
int ListLength();
void ListInsert(int NewPosition,int NewItem,bool& Success);
void ListDelete(int Position,bool& Success);
void ListRetrieve(int Position,int& DataItem,bool& Success);
void ListDisplay();

////////////////

Explanation / Answer

StackADT.h
#include
#include


//Stack ADT Type Defintions
typedef struct node2
{
void* dataPtr;
struct node2* link;
} STACK_NODE;

typedef struct
{
int count;
STACK_NODE* top;
} STACK;


/* ADT Prototype Declarations */
STACK* createStack (void);
bool pushStack (STACK* stack, void* dataInPtr);
void* popStack (STACK* stack);
void* stackTop (STACK* stack);
bool emptyStack (STACK* stack);
bool fullStack (STACK* stack);
int stackCount (STACK* stack);
STACK* destroyStack (STACK* stack);

/*========== createStack ==============
This algorithm creates an empty stack.
Pre Nothing
Post Returns pointer to a null stack
-or- NULL if overflow
*/
STACK* createStack (void)
{
// Local Definitions
STACK* stack;

// Statements
stack = (STACK*) malloc( sizeof (STACK));
if (stack)
{
stack->count = 0;
stack->top = NULL;
} // if
return stack;
} // createStack


/*============ pushStack ================
This function pushes an item onto the stack.
Pre stack is a pointer to the stack
dataPtr pointer to data to be inserted
Post Data inserted into stack
Return true if successful
false if underflow
*/
bool pushStack (STACK* stack, void* dataInPtr)
{
// Local Definitions
STACK_NODE* newPtr;

// Statements
newPtr = (STACK_NODE* ) malloc(sizeof( STACK_NODE));
if (!newPtr)
return false;

newPtr->dataPtr = dataInPtr;

newPtr->link = stack->top;
stack->top = newPtr;

(stack->count)++;
return true;
} // pushStack


/*============= popStack ==================
This function pops item on the top of the stack.
Pre stack is pointer to a stack
Post Returns pointer to user data if successful
NULL if underflow
*/
void* popStack (STACK* stack)
{
// Local Definitions
void* dataOutPtr;
STACK_NODE* temp;

// Statements
if (stack->count == 0)
dataOutPtr = NULL;
else
{
temp = stack->top;
dataOutPtr = stack->top->dataPtr;
stack->top = stack->top->link;
free (temp);
(stack->count)--;
} // else
return dataOutPtr;
} // popStack


/*============ stackTop =================
Retrieves data from the top of stack without
changing the stack.
Pre stack is a pointer to the stack
Post Returns data pointer if successful
null pointer if stack empty
*/
void* stackTop (STACK* stack)
{
// Statements
if (stack->count == 0)
return NULL;
else
return stack->top->dataPtr;
} // stackTop


/*============ emptyStack ================
This function determines if a stack is empty
Pre stack is pointer to a stack
Post returns 1 if empty; 0 if data in stack
*/
bool emptyStack (STACK* stack)
{
// Statements
return (stack->count == 0);
} // emptyStack


/*============== fullStack =================
This function determines if a stack is full.
Full is defined as heap full.
Pre stack is pointer to a stack head node
Return true if heap full
false if heap has room
*/
bool fullStack (STACK* stack)
{
// Local Definitions
STACK_NODE* temp;

// Statements
if ((temp =
(STACK_NODE*)malloc (sizeof(*(stack->top)))))
{
free (temp);
return false;
} // if

// malloc failed
return true;
} // fullStack

/*============== stackCount =================
Returns number of elements in stack.
Pre stack is a pointer to the stack
Post count returned
*/
int stackCount (STACK* stack)
{
// Statements
return stack->count;
} // stackCount

/*============= destroyStack =================
This function releases all nodes to the heap.
Pre A stack
Post returns null pointer
*/STACK* destroyStack (STACK* stack)
{
// Local Definitions
STACK_NODE* temp;

// Statements
if (stack)
{
// Delete all nodes in stack
while (stack->top != NULL)
{
// Delete data entry
free (stack->top->dataPtr);

temp = stack->top;
stack->top = stack->top->link;
free (temp);
} // while

// Stack now empty. Destroy stack head node.
free (stack);
} // if stack
return NULL;
} // destroyStack


CODE:

#include
#include
#include
#include
#include "stacksADT.h"

int main(void)
{

bool done = false;
char* dataPtr,*str;
int i, N;

STACK* stack;

stack = createStack();

while (!done)
{
dataPtr = (char*) malloc (sizeof(char));
printf ("Enter a word or /uN for undoing N words or /x to exit: ");

scanf("%s",dataPtr);

while(N--)
{
popStack(stack);
}

if (strcmp(dataPtr,"/x")==0 || fullStack (stack))//user quits entering
>
else //user wants to enter more words or undo
{

//undo part
if(strncmp(dataPtr,"/u",2)==0)//check first two entered characters if undo
{
//we are undoing. Let's get N

N = atoi(dataPtr+2); //convert string to integer

dataPtr=(char*)popStack(stack);//undo of last N words

//print message if N greater than number of words

} //if

else // user wants to enter a word
{

pushStack(stack, dataPtr);// push in to stack
}
} //else
} // while

//transfer to new stack and print it out
while(!emptyStack(stack))
{
dataPtr=(char*)popStack(stack);
printf("%s ", dataPtr);
free(dataPtr);
}

destroyStack(stack);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.