Evaluation of Binary Expression Tree

Evaluation of Expression Tree

#include<stdio.h>

#include<malloc.h>

#include<math.h>

#include<ctype.h>

struct node

{

            char data;

            struct node *lchild;

            struct node *rchild;

};

typedef struct node * NODE;

NODE getnode()

{

    NODE x;

    x = (NODE)malloc(sizeof(struct node));

    x->lchild =NULL;

    x->rchild = NULL;

    return x;

}

NODE create_tree(char postfix[])

{

            NODE temp, s[70];

            char symb;

            int i, top = -1;

            for(i=0; postfix[i] != '\0' ; i++)

            {

                        symb = postfix[i] ;

                        temp = getnode();

                        temp->data = symb;

                        if(isalnum(symb))

                        {

                                                s[++top] = temp;    //push operand to the stack

                        }

                        else

                        {

                                                temp->rchild = s[top--];    //pop second operand from stack and make it rchild

                                                temp->lchild = s[top--];    // pop first operand from stack and make it lchild

                                                s[++top] = temp;            //push operator node to stack

                        }

            }

            return s[top--];        //return the root of expression tree

}

float evaluate(NODE root)

{

            float num;

            switch(root->data)

            {

                        case '+': return evaluate(root->lchild)+evaluate(root->rchild);

                        case '-': return evaluate(root->lchild)-evaluate(root->rchild);

                        case '*': return evaluate(root->lchild)*evaluate(root->rchild);

                        case '/': return evaluate(root->lchild)/evaluate(root->rchild);

                        case '^':

                        case '$': return  pow(evaluate(root->lchild),evaluate(root->rchild));

                        default: if(isalpha(root->data))

                                    {

                                                printf("\n%c = ", root->data);

                                                scanf("%f", &num);

                                                return num;

                                    }

                                    else

                                                return root->data  - '0';

            }

}

void main()

{

            char postfix[60];

            float res;

            NODE root = NULL;

            printf("\nEnter the postfix expression: ");

            scanf("%s", postfix);

            root = create_tree(postfix);

            res = evaluate(root);

            printf("\nResult of expression is = %f", res);

}

Output:

Case 1:

Enter the postfix expression: 632-5*+1^7+

Result of expression is = 18.000000

Case 2:

Enter the postfix expression: abc-d*+e^f+

e = 1

a = 6

b = 3

c = 2

d = 5

f = 7

Result of expression is = 18.000000

Breadth First Search (BFS)

Breadth First Search (BFS)

#include<stdio.h>

#include<stdlib.h>

void bfs(int v);

int a[50][50], n, visited[50];

int q[20], front = -1,rear = -1;

void creategraph()

{

            int i, j;

            printf("\nEnter the number of vertices in graph:  ");

            scanf("%d",&n);

            printf("\nEnter the adjacency matrix:\n");

            for(i=1; i<=n; i++)

                        for(j=1;j<=n;j++)

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

}

void bfs(int v)

{

            int i, cur;

            visited[v] = 1;

            q[++rear] = v;

            printf("\nNodes reachable from starting vertex %d are: ", v);

            while(front!=rear)

            {

                        cur = q[++front];

                        for(i=1;i<=n;i++)

                        {

                                    if((a[cur][i]==1)&&(visited[i]==0))

                                    {

                                        q[++rear]=i;

                                                visited[i]=1;

                                                printf("%d ", i);

                                    }

                        }

            }

}

int main()

{

            int ch, start, i, j;

            creategraph();

            for(i=1;i<=n;i++)

                        visited[i]=0;

            printf("\nEnter the starting vertex: ");

            scanf("%d", &start);

             bfs(start);

             for(i=1;i<=n;i++)

             {

                                    if(visited[i]==0)

                                                printf("\nThe vertex that is not reachable is %d" ,i);

             }

}

Output:

Enter the number of vertices in graph:  4

Enter the adjacency matrix:

0          1          0          1

0          0          1          0

0          0          0          1

0          0          0          0

Enter the starting vertex: 1

Nodes reachable from starting vertex 1 are: 2 4 3

Enter the number of vertices in graph:  4

Enter the adjacency matrix:

0          1          0          1

0          0          1          0

0          0          0          1

0          0          0          0

Enter the starting vertex: 2

Nodes reachable from starting vertex 2 are: 3 4

The vertex that is not reachable is 1

Depth First Search (DFS)

Depth First Search

#include<stdio.h>

#include<stdlib.h>

void dfs(int v);

int a[50][50], n, visited[50];

int s[20], top = -1, count=0;

void creategraph()

{

            int i, j;

            printf("\nEnter the number of vertices in graph:  ");

            scanf("%d",&n);

            printf("\nEnter the adjacency matrix:\n");

            for(i=1; i<=n; i++)

                        for(j=1;j<=n;j++)

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

}

void dfs(int v)

{

            int i;

            visited[v]=1;

            s[++top] = v;

            for(i=1;i<=n;i++)

            {

                        if(a[v][i] == 1&& visited[i] == 0 )

                        {

                                    dfs(i);

                                    count++;

                        }

            }

}

int main()

{

            int ch, start, i, j;

            creategraph();

            for(i=1;i<=n;i++)

                        visited[i]=0;

            printf("\n Enter the starting vertex:\t");

            scanf("%d", &start);

            dfs(start);

            printf("\nNodes reachable from starting vertex %d are:\n", start);

            for(i=1;i<=count;i++)

                        printf("%d\t", s[i]);

}

Output:

Enter the number of vertices in graph:  4

Enter the adjacency matrix:

0          1          0          1

0          0          1          0

0          0          0          1

0          0          0          0

Enter the starting vertex:     1

Nodes reachable from starting vertex 1 are:

2       3       4

Enter the number of vertices in graph:  4

Enter the adjacency matrix:

0          1          0          1

0          0          1          0

0          0          0          1

0          0          0          0

Enter the starting vertex:     2

Nodes reachable from starting vertex 2 are:

3       4

Radix Sort

C program to sort an array elements using Radix Sort

#include<stdio.h>

#include<stdlib.h>

struct node

{

    int info ;

    struct node *link;

};

typedef struct node * NODE;

NODE bucket[10];

int n, a[20];

int largest()

{

    int i, large = a[0];

    for(i=0;i<n;i++)                        /*First find the largest number in the array*/

    {

        if(a[i] > large)

            large = a[i];

    }

    return large;

}

void insert_rear(int item, int rem)

{

      NODE cur, tmp;

      tmp = (NODE)malloc(sizeof(struct node));

      tmp->info = item;

      tmp->link = NULL;

      if(bucket[rem] == NULL)

      {

            bucket[rem] = tmp;

            return;

      }

      else

      {

           cur = bucket[rem];

           while(cur->link != NULL)

          {

                 cur = cur->link;

           }

           cur->link = tmp;

      }

}

void radix_sort()

{

        NODE p;

        int i, m,k, large, pass = 0, rem, divisor=1, j;

        large = largest();      /*largest number in the array*/

        printf("\nLargest Element is %d", large);

        while(large != 0)           /*Finds number of digits in the largest number*/

        {

            pass++;

            large = large/10 ;

        }

        printf("\nNumber of passes are %d", pass);

        for(m=1; m<=pass; m++)

        {

               printf("\n\n::::Pass %d::::", m);

               for(i=0;i<=9;i++)           /*initialize the buckets: Total 9 buckets*/

                      bucket[i] = NULL;

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

               {

                     rem = (a[i] / divisor) %10;

                     insert_rear(a[i], rem);

               }

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

              {

                    printf("\nbucket(%d) -> ",i);

                    p = bucket[i];

                    while(p!=NULL)

                   {

                           printf("%d ",p->info);

                           p = p->link;

                    }

              }

            /*Taking the elements of linked lists in array*/

             i = 0;

             for(k=0;k<=9;k++)

             {

                  p = bucket[k];

                  while(p!=NULL)

                 {

                      a[i++] = p->info;

                      p = p->link;

                 }

            }

            divisor = divisor*10;

        }

}

void main()

{

    int i;

    printf("\nEnter the number of elements in the list : ");

    scanf("%d",&n);

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

    {

        printf("\nEnter element %d : ",i+1);

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

    }

    printf("\nUnsorted list is :\n");

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

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

    radix_sort();

    printf("\nSorted list is :\n");

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

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

}

Output:

Enter the number of elements in the list : 10

Enter element 1 : 179

Enter element 2 : 208

Enter element 3 : 306

Enter element 4 : 93

Enter element 5 : 859

Enter element 6 : 984

Enter element 7 : 55

Enter element 8 : 9

Enter element 9 : 271

Enter element 10 : 33

Unsorted list is :

179   208   306   93   859   984   55   9   271   33

Largest Element is 984

Number of passes are 3

::::Pass 1::::

bucket(0) ->

bucket(1) -> 271

bucket(2) ->

bucket(3) -> 93 33

bucket(4) -> 984

bucket(5) -> 55

bucket(6) -> 306

bucket(7) ->

bucket(8) -> 208

bucket(9) -> 179 859 9

::::Pass 2::::

bucket(0) -> 306 208 9

bucket(1) ->

bucket(2) ->

bucket(3) -> 33

bucket(4) ->

bucket(5) -> 55 859

bucket(6) ->

bucket(7) -> 271 179

bucket(8) -> 984

bucket(9) -> 93

::::Pass 3::::

bucket(0) -> 9 33 55 93

bucket(1) -> 179

bucket(2) -> 208 271

bucket(3) -> 306

bucket(4) ->

bucket(5) ->

bucket(6) ->

bucket(7) ->

bucket(8) -> 859

bucket(9) -> 984

Sorted list is :

9   33   55   93   179   208   271   306   859   984

Address Calculation Sort

C Program to sort array elements using Address Calculation Sort

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

struct node
{
       int info;
       struct node *link;
};
typedef struct node * NODE;
NODE head[10];
int n,i,a[20];

int hash_fn(int number,  int k)
{
             /*Find kth digit of the number :example: if its 356 then kth digit will be 3 or if its 29 then kth digit will be 2*/
        int digit, i;
        for(i = 1 ; i <=k ; i++)
        {
              digit = number % 10 ;
              number = number /10 ;
        }
        return digit;       //address
}


/* Finds number of digits in the largest element of the list */
int large_dig()
{
       int large = a[0],ndig = 0 ;
       for(i=0;i<n;i++)                        /*First find the largest number in the array*/
      {
              if(a[i] > large)
                      large = a[i];
       }
       printf("\nLargest Element is %d",large);

      while(large != 0)           /*Finds number of digits in the largest number*/
      {
               ndig++;
               large = large/10 ;
      }
      printf("\nNumber of digits in it are %d", ndig);
      return(ndig);
}


/*Inserts the number in linked list in sorted manner*/
void insert(int num, int addr)
{
      NODE cur ,tmp;
      tmp = (NODE)malloc(sizeof(struct node));
      tmp->info = num;

      /*list empty or item to be added in beginning */
       if(head[addr] == NULL || num < head[addr]->info)
      {
            tmp->link = head[addr];
            head[addr] = tmp;
            return;
      }
     else
     {
            cur = head[addr];
            while(cur->link != NULL && cur->link->info < num)
                      cur = cur->link;
            tmp->link = cur->link;
            cur->link = tmp;
     }
}

void addr_sort()
{
       int i, k, dig, addr;
       NODE p;
       k = large_dig();        /*number of digits in the largest number*/
       for(i=0;i<=9;i++)
               head[i]=NULL;
       for(i=0;i<n;i++)
      {
               addr = hash_fn(a[i], k);
               insert(a[i], addr);
       }

      for(i=0; i<=9 ; i++)
      {
              printf("\nhead(%d) -> ", i);
              p = head[i];
              while(p!=NULL)
             {
                    printf("%d ", p->info);
                    p = p->link;
              }
      }
     /*Taking the elements of linked lists in array*/
      i = 0;
      for(k=0;k<=9;k++)
      {
               p = head[k];
               while(p!=NULL)
              {
                       a[i++] = p->info;
                       p = p->link;
               }
      }
}

void main()
{
      int i;
      printf("\nEnter the number of elements in the list : ");
      scanf("%d", &n);
      for(i=0;i<n;i++)
      {
             printf("\nEnter element %d : ",i+1);
             scanf("%d",&a[i]);
      }

      printf("\nUnsorted list is :\n");
      for(i=0;i<n;i++)
            printf("%d ",a[i]);

      addr_sort();
      printf("\nSorted list is :\n");
      for(i=0;i<n;i++)
              printf("%d ",a[i]);
}


Output:

Enter the number of elements in the list : 15
Enter element 1 : 12
Enter element 2 : 345
Enter element 3 : 567
Enter element 4 : 367
Enter element 5 : 789
Enter element 6 : 23
Enter element 7 : 15
Enter element 8 : 56
Enter element 9 : 567
Enter element 10 : 899
Enter element 11 : 123
Enter element 12 : 321
Enter element 13 : 678
Enter element 14 : 67
Enter element 15 : 45
Unsorted list is :
12   345   567  367   789   23   15   56   567   899   123   321   678   67   45
Largest Element is 899
Number of digits in it are 3

head(0) -> 12  15  23  45  56  67
head(1) -> 123
head(2) ->
head(3) -> 321  345  367
head(4) ->
head(5) -> 567  567
head(6) -> 678
head(7) -> 789
head(8) -> 899
head(9) ->
Sorted list is :
12   15   23   45   56   67   123   321   345   367   567   567   678   789  899

Insertion Sort

C Program to sort the elements using Insertion Sort

#include<stdio.h>
int n, a[20];

void insertion_sort()
{
       int i, j, temp;
       for(i=1; i<n ;i++)
      {
              temp = a[i];
              j = i-1;
              while(j>=0 &&  temp < a[j])
             {
                    a[j+1] = a[j];
                    j = j-1;
             }
             a[j+1] = temp;
       }
}

void main()
{
       int i;
       printf("\nEnter the number of elements: ");
       scanf("%d",&n);

      printf("\nEnter the array elements:");
      for(i=0;i<n;i++)
           scanf("%d", &a[i]);

      insertion_sort();

     printf("\nThe array elements after insertion sort: ");
     for(i=0;i<n;i++)
            printf("%d ", a[i]);
}

Output:
Enter the number of elements: 7
Enter the array elements:  89     45      68       90       29       34       17
The array elements after insertion sort: 17       29       34         45        68        89       90