Sum of Subsets (find all sums for given Number set)

CodeProject

Sample Output is shown above. This program will run in windows only. For Linux you must write your own gotoxy function.

#include<stdio.h>

#include<stdlib.h>

#define MAX_PRINT_LEVEL 5

#include <windows.h>

void gotoxy(int col, int row)     //starting from 0

{

    COORD coord;

    coord.X = col;

    coord.Y = row;

    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord);

}

struct tree_node

{

       struct tree_node *left,*right;

       int data;

};

typedef struct tree_node TNODE;

TNODE* create_tree(int *input,int num);

void add_num(TNODE *node,int *input,int num);

void print_tree(TNODE *root,int num,int col,int row);

int print_subsets(TNODE *root,int sum,int *input,int *subsets,int index,int num);

int pow(int a, int b);

//array to store all possible sums, remove if not neeeded

/*int *sums,sum_count=0;*/

int main()

{

       int sum;

       int *input,num;

       int *subsets;

       TNODE *root=NULL;

       int i;

       printf("\nHOW MANY NUMBERS: ");

       scanf("%d",&num);

       if(num<0)

       {

              printf("\nERROR: Invalid num value...\n\n");

              exit(1);

       }

       if( (input = (int*)malloc(num*sizeof(int))) == NULL)

       {

              printf("\n\nERROR: MEMORY NOT ALLOCATED\n\n");

              exit(1);

       }

       if( (subsets = (int*)malloc(num*sizeof(int))) == NULL)

       {

              printf("\n\nERROR: MEMORY NOT ALLOCATED\n\n");

              exit(1);

       }

       printf("\nEnter numbers: \n");

       for(i=0;i<num;i++)

       {

              printf("NUM[%d] : ",i);

              scanf("%d",&input[i]);

       }

       //array to store all possible sums, remove if not neeeded

       /*if( (sums = (int*)malloc(pow(2,num)*sizeof(int))) == NULL)

       {

              printf("\n\nERROR: MEMORY NOT ALLOCATED\n\n");

              exit(1);

       }*/

       root = create_tree(input,num);

       system("cls");

       print_tree(root,num,0,0);

       printf("\n\nINPUT ARRAY :");

       for(i=num-1;i>=0;i--)

              printf(" %d",input[i]);

      

       printf("\n\n");

       //print all sums possible

       /*for(i=sum_count-1;i>=0;i--)

       {

              if(print_subsets(root,sums[i],input,subsets,num,num))

                     printf("\n********** SUBSETS WITH SUM = %d **********",sums[i]);

       }*/

       //print  a particular sum

       printf("\n\nENTER SUM: ");

       scanf("%d",&sum);

       printf("\n********** SUBSETS WITH SUM = %d **********",sum);

       if(!print_subsets(root,sum,input,subsets,num,num))

              printf("\n\nOOPS : NO SUBSET CAN BE FOUND");

       printf("\n\n\n");

       return 0;

}

int print_subsets(TNODE *node,int sum,int *input,int *subsets,int index,int num)

{

       int i,found=0,a,b;

       if(node->left==NULL && node->right == NULL)

       {

              if(node->data == sum)

              {

                     printf("\n{ ");

                     for(i=0;i<num;i++)

                           if(subsets[i] == 1)

                           {

                                  found = 1;

                                  printf("%d,",input[i]);

                           }

                     if(found)

                           printf("\b } ");

                     else

                           printf("NULL SET }");

                     return 1;

              }

              else

                     return 0;

       }

       if(node->left)

       {

              subsets[index-1] = 1;

              a=print_subsets(node->left,sum,input,subsets,index-1,num);

       }

       if(node->right)

       {

              subsets[index-1] = 0;

              b=print_subsets(node->right,sum,input,subsets,index-1,num);

       }

       return (a||b);

}

void print_tree(TNODE *root,int level,int col,int row)

{

       int gap,pos,slash;

       int i;

       int bcol,brow;

       if(level>MAX_PRINT_LEVEL)

       {

              printf("\nTree cant be displayed for level > %d...",MAX_PRINT_LEVEL);

              return;

       }

       gap = pow(2,level) - 1;

       bcol = col;

       brow = row;

       col=col+gap;

       gotoxy(col,row);

       printf("%d",root->data);

       if(root->left)

       {

              slash = pow(2,level-1);

              for(i=0;i<slash;i++)

              {

                     gotoxy(--col,++row);

                     printf("/");

              }

              print_tree(root->left,level-1,bcol,row+1);

       }

       if(root->right)

       {

              col = bcol+gap;

              row = brow;

              slash = pow(2,level-1);

              for(i=0;i<slash;i++)

              {

                     gotoxy(++col,++row);

                     printf("\\");

              }

              if(level>1)

                     print_tree(root->right,level-1,bcol+gap+1,row+1);

              else

                     print_tree(root->right,level-1,bcol+gap+1,row+2);

       }

}

int pow(int a, int b)

{

       int ans=1;

       if(b==0)

              return 1;

       while(b>0)

       {

              ans = ans * a;

              b--;

       }

       return ans;

}

TNODE* create_tree(int *input,int num)

{

       TNODE *temp;

       int i;

       temp = (TNODE*)malloc(1*sizeof(TNODE));

       temp->data=0;

       temp->left=NULL;

       temp->right=NULL;

       add_num(temp,input,num);

       return temp;

}

void add_num(TNODE *node,int *input,int num)

{

       if(num == 0)

       {

              //array to store all possible sums, remove if not neeeded

              /*sums[sum_count++] = node->data;*/

              return;

       }

       node->left=(TNODE*)malloc(1*sizeof(TNODE));

       node->right=(TNODE*)malloc(1*sizeof(TNODE));

       node->left->data = node->data + input[num-1];

       node->left->left = NULL;

       node->left->right = NULL;

       node->right->data = node->data + 0;

       node->right->left = NULL;

       node->right->right = NULL;

       add_num(node->left,input,num-1);

       add_num(node->right,input,num-1);

}

INFIX to POSTFIX conversion

CodeProject

#define MAX 255

struct list

{

    char c;                     //store a character here

    struct list *prev;          //pointer to previou element

};

struct stack

{

    struct list *top;           //stack top pointer

    struct list *start;         //stack start(base) pointer

};

void push(struct stack *top,char c);

void pop(struct stack *top, char *c);

void push(struct stack *stk, char c)

{

    struct list *temp;

    temp = (struct list*)malloc(1*sizeof(struct list));

    temp->c = c;

    temp->prev = stk->top;

    stk->top = temp;

}

void pop(struct stack *stk,char *c)

{

    struct list *temp;

    *c = stk->top->c;

    temp = stk->top;

    stk->top = temp->prev;

    free(temp);

}

//precedence function for operators

int prec(char a);

char* to_postfix(char *str)

{

    struct stack stk;

    char post[MAX],*p,ch,*backup;

    //post[] is a string that will have post fix string

    //p is pointer to it.

    //backup is a pointer to input string that will be user later to copy post[] to *str

    p = post;

    backup = str;

    //create a stack

    stk.start = (struct list*)malloc(1*sizeof(struct list));

    //initially start == top

    stk.top = stk.start;

    //since no item is in stack prev of both top & stack is NULL

    stk.start->prev = NULL;

    stk.top->prev = NULL;

    while(*str!='\0')

    {

        //if operand add it to o/p string

        if( isalnum(*str) )

            *p++ = *str++;

        else if(*str == '(' || *str == '+' || *str == '-' || *str == '*' || *str == '/')

        {

            //if '(' push it directly

            if( *str == '(' )

                push(&stk,*str++);

            //push higher precedence operator

            else if( stk.start==stk.top || (prec(*str) > prec(stk.top->c)))

                push(&stk,*str++);

            else

            {

                //pop operators from stack till we get lesser precedence operator or empty stack

                while( ( prec(*str) <= prec(stk.top->c) ) && (stk.top != stk.start) )

                    pop(&stk,p++);

                //now push current opreator from i/p string

                push(&stk,*str++);

            }

        }

        //if closing bracket in input string encountered

        else if(*str == ')' )

        {

            //then while we encounter opening bracket or reach start of stack

            while(stk.top != stk.start)

            {

                if(stk.top->c == '(')

                {

                    //just pop ')' in a dummy variable and break out of loop

                    pop(&stk,&ch);

                    break;

                }

                else

                    //keep popping operators and adding to o/p string if '(' not found

                    pop(&stk,p++);

            }

            //check that last item popped was a matching '('

            if(ch != '(')

            {

                printf("\nERROR: ')' NOT MATCHED...EXITING\n");

                exit(1);

            }

            //go to next char in input string on matching ')'

            str++;

        }

        //ignore white spaces

        else if(*str == ' ' || *str == '\t')

            str++;

        //if unexpected operator then exit

        else

        {

            printf("\n\nERROR : \"%c\" -> WRONG INPUT...EXITING\n",*str);

            exit(1);

        }

    }

    //now pop any remaing opeartors in stack and add them to o/p string

    while(stk.top != stk.start)

    {

        pop(&stk,p);

        //check that last item popped was a matching '('

        //if so then we have extra '('

        if(*p == '(')

        {

            printf("\nERROR: '(' NOT MATCHED...EXITING\n");

            exit(1);

        }

        p++;

    }

    *p = '\0';

    //now we need to copy because post[] is destroyed and can be overwritten

    //as soon as we return from this function

    strcpy(backup,post);

    return backup;

}

int prec(char a)

{

    //make '(' lowest precedence so that it is not popped by any other opeartor

    if(a=='(')

        return 1;

    if(a == '+' || a == '-')

        return 2;

    else if (a == '/' || a == '*')

        return 3;

    return 0;

}

SORT a LINKED LIST containing STRINGS

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

typedef struct STR_DATA
{
    char *name;
    struct STR_DATA *next;
}NODE;

int count=0;
void add_names(NODE **head);
void sort_names(NODE *head);
void print_names(NODE *head);
char printmenu(NODE *head);

int main()
{
    NODE *head=NULL;
    char ch='y';
    int flag=1;

    while(flag)
    {
        ch = printmenu(head);
        switch(ch)
        {
            case '0':
                    printf("\n\nEXITING...");
                    flag = 0;
                    break;
            case '1':
                    while ((ch = getchar()) != '\n' && ch != EOF);
                    add_names(&head);
                    break;
            case '2':
                    while ((ch = getchar()) != '\n' && ch != EOF);
                    sort_names(head);
                    break;
            default:
                    printf("\n\nENTER VALID CHOICE...");
                    break;   
        }
       
    }

    printf("\n\n");
    system("wait");
    printf("\n");
    return 0;
}
char printmenu(NODE *head)
{
    char ch;

    printf("\nCurrent list: ");
    print_names(head);
    printf("\nWHAT TO DO: ");
    printf("\n[1] ADD a name\n[2] SORT names");
    printf("\n\nEnter choice: ");
    scanf("%c",&ch);

    return ch;
}
void add_names(NODE **head)
{
    NODE *new_node;
    int num_char=0;
    char *str1=NULL,ch='x';

    new_node =(NODE*)malloc(1*sizeof(NODE));
    count++;
    new_node->next=*head;
    *head=new_node;

    printf("\nEnter name : ");   
    while(ch!='\n' && ch != EOF)
    {
        ch=getchar();
        if(ch=='\n')
            break;
       
        num_char++;
        str1 = (char*)realloc( str1,(num_char+1)*sizeof(char));
        if(str1 == NULL)
        {
            printf("\nERROR: reallocating memory...\n\n");
            exit(1);
        }

        str1[num_char-1]=ch;
        str1[num_char]='\0';
    }
   
    new_node->name = (char*)malloc((num_char+1)*sizeof(char));
    strcpy(new_node->name,str1);
    free(str1);
}

void sort_names(NODE *head)
{
    int i,j;
    NODE *curr,*prev;
    char *temp1,*temp2;

    for(i=0;i<count-1;i++)
    {
        prev=head;
        curr=head->next;               
        for(j=0;j<count-1-i;j++)
        {
            if(strcmp(prev->name,curr->name) > 0)
            {
                temp1 = (char*)malloc(strlen(prev->name));
                temp2 = (char*)malloc(strlen(curr->name));
                strcpy(temp1,prev->name);
                strcpy(temp2,curr->name);

                curr->name = (char*)realloc(curr->name,strlen(temp1));
                prev->name = (char*)realloc(prev->name,strlen(temp2));
                strcpy(prev->name,temp2);
                strcpy(curr->name,temp1);
                free(temp1);
                free(temp2);
            }
            prev=curr;
            curr=curr->next;
        }
    }
}

void print_names(NODE *head)
{
    if(!head)
    {
        printf("EMPTY");
        return;
    }
    while(head)
    {
        printf("%s|",head->name);
        head=head->next;
    }
}