Thursday 17 November 2016

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