Search This Blog

Simplicity is the ultimate sophistication.” — Leonardo da Vinci
Contact me: sreramk360@gmail.com

Monday, 30 March 2015

Example program that imitiates 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;
}
copyright (c) 2015 K Sreram. 
About my blog

No comments:

Post a Comment

Featured post

Why complicating matters is not good

“ Simplicity is the ultimate sophistication.” — Leonardo da Vinci Why is complicating things wrong ? - K Sr...