As discussed in class, the run-time handling of method calls uses a stack of act

Question

As discussed in class, the run-time handling of method calls uses a stack of activation records. This stack is managed by the system. In this project, you will be using an explicitly maintained stack to simulate recursion. The objects on the stack will be instances of an ActivationRecord class. ou Wi As an example, consider the class FactorialCalculatorWithStack. This class implements the FactorialCalculator interface (which declares a single method: factorial(int n)) In particular, compare the implementation of the factorial method in this class with the implementation in the class RecursiveFactorialCalculator. Note that the method uses a stack of objects in an inner class ActivationRecord that closely simulates the run time stack for the recursive method. (The major difference is that objects use a returnPoint within the code in place of the returnAddress used on the run-time stack. Note that this implementation of factorial uses a switch statement based on various points in the recursive method, including all return points. (Note: instead of a return address in the calling method, this return-point mechanism uses a point within the method that does any needed final processing before the return. In this project, you will be producing a similar non-recursive implementation of a method to play the Towers of Hanoi. I have provided the recursive version to help you in modeling the recursive process for the Towers of Hanoi. Please note that the recursive code has two recursive calls, whereas the recursive factorial method had only one. (How will this affect your simulation?) Also, please note that the ActivationRecord class for the Towers of Hanoi will be different from the one for Factorial Calculator

Explanation / Answer

Stack uisng arrays:

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#define size 100
int top=-1;
int flag=0;
int stack[size];
void push(int *,int);
int pop(int *);
void display(int *);
void push(int s[],int d)
{
if(top==(size-1))
flag=0;
else
{
flag=1;
++top;
s[top]=d;
}
}
int pop(int s[])
{
int popped_node;
if(top==-1)
{
popped_node=0;
flag=0;
}
else
{
flag=1;
popped_node=s[top];
--top;
}
return(popped_node);
}
void display(int s[])
{
int j;
if(top==-1)
{
printf(" stack is empty");
}
else
{
for(j=top;j>=0;--j)
printf(" %d",s[j]);
}
}

void main()
{
int data;
char ch ;
int q=0;
int top=-1;
clrscr();
do
{
printf(" push->i pop->p quit->q:");
printf("enter your choice");
do
{
ch =getchar();
ch =tolower(ch );
}
while(strchr("ipq",ch )==NULL);
printf("your choice is %c",ch );
switch(ch )
{
case'i':printf(" input element to push");
scanf("%d",&data);
push(stack,data);
if(flag)
{
printf(" after inserting ");
display(stack);
if(top==(size-1))
printf(" stack is full");
}
else
printf(" stack is over-flow after pushing");
break;
case 'p':data=pop(stack);
if(flag)
{
printf(" element is popped:%d",data);
printf(" now the stack is as follows : ");
display(stack);
}
else
printf(" stack is unde-rflow ");
break;
case'q':q=1;
}
}
while(!q);
}

STACK USING LINKED LIST WITH ADT OPERATIONS:

#include <stdio.h>
#include <stdlib.h>

struct node
{
int info;
struct node *ptr;
}*top,*top1,*temp;

int topelement();
void push(int data);
void pop();
void empty();
void display();
void destroy();
void stack_count();
void create();

int count = 0;

void main()
{
int no, choice, e;

printf(" 1 - Push");
printf(" 2 - Pop");
printf(" 3 - Top");
printf(" 4 - Empty");
printf(" 5 - Exit");
printf(" 6 - Dipslay");
printf(" 7 - Stack Count");
printf(" 8 - Destroy stack");

create();

while (1)
{
printf(" Enter choice : ");
scanf("%d", &choice);

switch (choice)
{
case 1:
printf("Enter data : ");
scanf("%d", &no);
push(no);
break;
case 2:
pop();
break;
case 3:
if (top == NULL)
printf("No elements in stack");
else
{
e = topelement();
printf(" Top element : %d", e);
}
break;
case 4:
empty();
break;
case 5:
exit(0);
case 6:
display();
break;
case 7:
stack_count();
break;
case 8:
destroy();
break;
default :
printf(" Wrong choice, Please enter correct choice ");
break;
}
}
}


void create()
{
top = NULL;
}


void stack_count()
{
printf(" No. of elements in stack : %d", count);
}


void push(int data)
{
if (top == NULL)
{
top =(struct node *)malloc(1*sizeof(struct node));
top->ptr = NULL;
top->info = data;
}
else
{
temp =(struct node *)malloc(1*sizeof(struct node));
temp->ptr = top;
temp->info = data;
top = temp;
}
count++;
}


void display()
{
top1 = top;

if (top1 == NULL)
{
printf("Stack is empty");
return;
}

while (top1 != NULL)
{
printf("%d ", top1->info);
top1 = top1->ptr;
}
}


void pop()
{
top1 = top;

if (top1 == NULL)
{
printf(" Error : Trying to pop from empty stack");
return;
}
else
top1 = top1->ptr;
printf(" Popped value : %d", top->info);
free(top);
top = top1;
count--;
}


int topelement()
{
return(top->info);
}

void empty()
{
if (top == NULL)
printf(" Stack is empty");
else
printf(" Stack is not empty with %d elements", count);
}


void destroy()
{
top1 = top;

while (top1 != NULL)
{
top1 = top->ptr;
free(top);
top = top1;
top1 = top1->ptr;
}
free(top1);
top = NULL;

printf(" All stack elements destroyed");
count = 0;
}

TOWERS OF HANAIO:

#include<conio.h>
#include<iostream>
#include<math.h>
using namespace std;
struct data1
{
int data1;
data1 *next1;
}*top1 = NULL, *p1 = NULL, *np1 = NULL;
struct data2
{
int data2;
data2 *next2;
}*top2 = NULL, *p2 = NULL, *np2 = NULL;
struct data3
{
int data3;
data3 *next3;
}*top3 = NULL, *p3 = NULL, *np3 = NULL;
void push1(int data)
{
np1 = new data1;
np1->data1 = data;
np1->next1 = NULL;
if (top1 == NULL)
{
top1 = np1;
}
else
{
np1->next1 = top1;
top1 = np1;
}
}
int pop1()
{
int b = 999;
if (top1 == NULL)
{
return b;
}
else
{
p1 = top1;
top1 = top1->next1;
return(p1->data1);
delete(p1);
}
}
void push2(int data)
{
np2 = new data2;
np2->data2 = data;
np2->next2 = NULL;
if (top2 == NULL)
{
top2 = np2;
}
else
{
np2->next2 = top2;
top2 = np2;
}
}
int pop2()
{
int b = 999;
if (top2 == NULL)
{
return b;
}
else
{
p2 = top2;
top2 = top2->next2;
return(p2->data2);
delete(p2);
}
}
void push3(int data)
{
np3 = new data3;
np3->data3 = data;
np3->next3 = NULL;
if (top3 == NULL)
{
top3 = np3;
}
else
{
np3->next3 = top3;
top3 = np3;
}
}
int pop3()
{
int b = 999;
if (top3 == NULL)
{
return b;
}
else
{
p3 = top3;
top3 = top3->next3;
return(p3->data3);
delete(p3);
}
}
int top_of_stack()
{
if (top1 != NULL && top1->data1 == 1 )
{
return 1;
}
else if (top2 != NULL && top2->data2 == 1)
{
return 2;
}
else if (top3 != NULL && top3->data3 == 1)
{
return 3;
}
}
void display1()
{
cout<<endl;
data1 *p1;
p1 = top1;
cout<<"Tower1-> "<<" ";
while (p1 != NULL)
{
cout<<p1->data1<<" ";
p1 = p1->next1;
}
cout<<endl;
}
void display2()
{
data2 *p2;
p2 = top2;
cout<<"Tower2-> "<<" ";
while (p2 != NULL)
{
cout<<p2->data2<<" ";
p2 = p2->next2;
}
cout<<endl;
}
void display3()
{
data3 *p3;
p3 = top3;
cout<<"Tower3-> "<<" ";
while (p3 != NULL)
{
cout<<p3->data3<<" ";
p3 = p3->next3;
}
cout<<endl;
cout<<endl;
}
void toh(int n)
{
int i, x, a, b;
for (i = 0; i < (pow(2,n)); i++)
{
display1();
display2();
display3();
x = top_of_stack();
if (i % 2 == 0)
{
if (x == 1)
{
push3(pop1());
}
else if (x == 2)
{
push1(pop2());
}
else if (x == 3)
{
push2(pop3());
}
}
else
{
if (x == 1)
{
a = pop2();
b = pop3();
if (a < b && b != 999)
{
push3(b);
push3(a);
}
else if (a > b && a != 999)
{
push2(a);
push2(b);
}
else if (b == 999)
{
push3(a);
}
else if (a == 999)
{
push2(b);
}
}
else if (x == 2)
{
a = pop1();
b = pop3();
if (a < b && b != 999)
{
push3(b);
push3(a);
}
else if (a > b && a != 999)
{
push1(a);
push1(b);
}
else if (b == 999)
{
push3(a);
}
else if (a == 999)
{
push1(b);
}
}
else if (x == 3)
{
a = pop1();
b = pop2();
if (a < b && b != 999)
{
push2(b);
push2(a);
}
else if (a > b && a != 999)
{
push1(a);
push1(b);
}
else if (b == 999)
{
push2(a);
}
else if (a == 999)
{
push1(b);
}
}
}
}
}
int main()
{
int n, i;
cout<<"enter the number of disks ";
cin>>n;
for (i = n; i >= 1; i--)
{
push1(i);
}
toh(n);
getch();
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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