An example program that imitates function stack
An example program that imitates function stack
Program:
/*
an example program that imitates the
"function stack" concept.
This program is already available as the
second program in these record
program series, but here recession is imitated
with a fake function stack!
#include
<stdio.h>
#include
<conio.h>
#include
<stdlib.h>
#include
<process.h>
enum BOOL {FALSE,
TRUE};
typedef int BOOL;
struct NODE;
struct FunctionData;
typedef struct NODE
Node;
typedef Node* PtrNode;
typedef PtrNode Stack;
typedef struct
FunctionData DataType;
struct FunctionData{
int *instant;
int depth;
int i;
};
struct NODE{
DataType data;
PtrNode next;
};
BOOL IsEmpty(Stack s)
{
return ((s!=NULL)&&(s->next ==
NULL));
}
Stack NewStack()
{
Stack s = malloc(sizeof(Node));
s->next = NULL;
return s;
}
PtrNode NewNode()
{
PtrNode n = malloc(sizeof(Node));
return n;
}
void Delete(PtrNode n)
{
free(n);
}
void Push(Stack s,
DataType data)
{
PtrNode n = NewNode();
if(n == NULL)
{
fprintf(stderr, "error: memory
allocation using malloc function failed");
return;
}
n->data = data;
n->next = s->next;
s->next = n;
}
DataType* Top(Stack s)
{
if(s==NULL || s->next == NULL) // this
is a fatal error
{
fprintf(stderr, "error: stack is
empty");
exit(-1);
}
return &(s->next->data);
}
void Pop(Stack s)
{
if(s==NULL || s->next == NULL) // this
is a fatal error
{
fprintf(stderr, "error: stack is
empty");
exit(-1);
}
PtrNode temp = s->next;
s->next = s->next->next;
Delete(temp);
}
DataType* TopAndPop
(Stack s)
{
DataType* top = Top(s);
Pop(s);
return top;
}
void PopAll(Stack s)
{
while (!IsEmpty(s))
Pop(s);
}
void
DisposeStack(Stack* s)
{
PopAll(*s);
Delete(*s);
*s = NULL;
}
///************************************************************************
int evaluateSum(int*
array, int size)
{
int i, s = 0;
for (i = 0; i<size; ++i)
s += array[i];
return s;
}
void display(int
*array, int size)
{
int i;
for (i = 0; i < size; ++i)
printf("\n%d", array[i]);
printf("\n\n");
}
int evaluate(DataType
BasefunData,const int *mainArray,
const int size_mainArray,
const int maxDepth,
const int result)
{
Stack FncStack = NewStack();
DataType temp;
unsigned long long int count = 0;
Push(FncStack, BasefunData);
Top(FncStack)->i = 0; // initialised to zero from the beginning
while(!IsEmpty(FncStack))
{
//if (Top(FncStack)->depth ==
0) count = 0; // this ensures that this
function can be used for a second time
// the above line is not needed
because 'count' is not
// required to be reinitialise
because here, 'count' is
// static instead of being dynamic
if (Top(FncStack)->depth ==
(maxDepth - 1)) // base case
{
int i;
for (i = 0;
i<size_mainArray; ++i)
{
Top(FncStack)->instant[Top(FncStack)->depth] = mainArray[i];
if (evaluateSum(Top(FncStack)->instant,
Top(FncStack)->depth+1) == result)
// condition is checked
and the combination is displayed
{
display(Top(FncStack)->instant, Top(FncStack)->depth+1);
++count;
}
}
Pop(FncStack);
continue;
}
if (Top(FncStack)->depth <
(maxDepth - 1))
{// originally, there was a for loop
here. but the for loop automatically
// gets implemented in this
implementation
if (
Top(FncStack)->i<size_mainArray)
{
Top(FncStack)->instant[Top(FncStack)->depth] =
mainArray[Top(FncStack)->i]; // this creates the array that's being checked
// the condition is checked in
the base case
++(Top(FncStack)->i);
temp.depth =
Top(FncStack)->depth + 1;
temp.instant =
Top(FncStack)->instant;
temp.i = 0; // initialise to zero like how
the 'i' value of the current iteration starts with zero
Push(FncStack, temp);
}
else
Pop(FncStack);
}
}
return count;
}
void getElements(int* array
, int size)
{
int i, r;
for(i = 0; i<size; ++i)
{
scanf("%d", &r);
array[i] = r;
}
}
/// this program runs
at O(2^(N+1)) time complexity and O(N) space complexity. The solution is
inefficient for larger values
int main()
{
int result;
int *mainArray;
int size_mainArray;
int *instantArray;
int size_instant;
DataType temp;
printf("enter the size of the main
array:");
scanf("%d",
&size_mainArray);
printf("\nenter the size of the
summation:");
scanf("%d", &size_instant);
mainArray =
malloc(sizeof(int)*size_mainArray);
instantArray =
malloc(sizeof(int)*size_instant);
printf("\nenter the elements: ");
getElements(mainArray, size_mainArray);
printf("enter result:");
scanf("%d", &result);
temp.instant = instantArray;
temp.depth = 0;
int count = evaluate(temp, mainArray,
size_mainArray, size_instant,result);
printf("\n number of combinations
possible: %d", count);
getch();
return 0;
No comments:
Post a Comment