EXPRESSION TREE program

CodeProject

#include<stdio.h>

#include<stdlib.h>

#define MAX 255

struct tree_node

{

       struct tree_node *left,*right;

       char c;

};

typedef struct tree_node TNODE;
 

struct tree

{

       TNODE *root;

};

struct tree btree;

void in_order_print(TNODE *node,TNODE *root);

/*********************************** EXP TREE FUNCTIONS *********************************/

struct tlist

{

    struct tree_node *node;     //a subtree root address is stored here

    struct tlist *prev;         //previous element in stack

};

struct tstack

{

    struct tlist *top;          //stack top pointer

    struct tlist *start;        //stack base pointer

};

void tpush(struct tstack *top,struct tree_node *node);

void tpop(struct tstack *top, struct tree_node **node);

void tpush(struct tstack *stk, struct tree_node *node)

{

    struct tlist *temp;

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

    temp->node = node;

    temp->prev = stk->top;

    stk->top = temp;

}

void tpop(struct tstack *stk,struct tree_node **node)

{

    struct tlist *temp;

    *node = stk->top->node;

    temp = stk->top;

    stk->top = temp->prev;

    free(temp);

}

struct tree_node* buildExpTree(char *str);

//function to convert infix to postfix expression

char* to_postfix(char *str);

struct tree_node* buildExpTree(char *str)

{

    struct tstack stk;

    struct tree_node *temp=NULL;

    str = to_postfix(str);  //see post for postfix conversion in blog

    //create a stack

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

    stk.top = stk.start;

    stk.start->prev = NULL;

    stk.top->prev = NULL;

    while(*str != '\0')

    {

        //create a tree with its root as temp

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

        //if *str is operand create a tree as single node only

        if( isalnum(*str) )

        {

            temp->left = NULL;          //no left and right childs

            temp->right = NULL;

        }

        //if operator is encountered pop previous 2 trees and make them current tree's childs

        else

        {

            tpop(&stk,&(temp->right));

            tpop(&stk,&(temp->left));

        }

        //now push current trees address

        tpush(&stk,temp);

              temp->c = *str++;

    }

    return temp;

}

void in_order_print(TNODE *node,TNOE *root)

{

       if(node->left)

              in_order_print(node->left,root);

        

       if(node == root)

              printf("[%c] ",node->c);

       else

              printf("%c ",node->c);

       if(node->right)

              in_order_print(node->right,root);

}

int main()

{

       char str[MAX];

       printf("\nEnter Expression string: ");

       gets(str);

       btree.root=buildExpTree(str);
       printf("\nIN ORDER TREE: ");

       in_order_print(btree.root,btree.root);

       printf("\n\n");
       return 0;

}

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;

}

IMPLEMENT Round Robin scheduling algoritm.

CodeProject This program is general and considers the case when no programs may be running also.

/*   AUTHOR     :    VINAY CHOUDHARY

     DATE       :    20-11-2010

     TITLE      :    ROUND ROBIN SCHEDULING ALGORITHM

     COMPANY    :   

     TIME       :   

*/

#include<stdio.h>

#include<stdlib.h>

#define NUM_PRC      5    //number of process

#define TIME_QUANTUM 3    //time quantum

#define CONTEXT_SWT  1    //context switch time between process, set 0 if not to be included

int ARR[NUM_PRC];    //arrival times of processes

int BRS[NUM_PRC];    //burst times of processes

int STR[NUM_PRC];    //start times

int FIN[NUM_PRC];    //finish times

int WAT[NUM_PRC];    //waiting times

int TRN[NUM_PRC];    //turn around times

void get_times();

void RR();

void calc(int *tt, int *tw,float *at,float *aw);

void print(int *tt, int *tw,float *at,float *aw);

int main()

{

     int TT,TW;             //total wait & turnaround times

     float avg_wat,avg_trn; //average wait & turnaround times

     get_times();

     RR();

     calc(&TT,&TW,&avg_wat,&avg_trn);

     print(&TT,&TW,&avg_wat,&avg_trn);

     printf("\n\n***** END OF RR *****\n\n");

     return 0;

}

void get_times()

{

     int i;

     printf("\n***** GETTING ARRIVAL & BURST TIMES *****\n");

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

     {

           STR[i] = -1;    //set this to -1 to mark it as not started

           printf("Enter arrival & burst time for process[%d] : ",i+1);

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

     }

}

void RR()

{

     int exc_time=0;        //initially execution time is 0

     int remain=NUM_PRC;    //unterminated processes

     int t_BRS[NUM_PRC];    //temporary BRS ARRAY

     int i;

     int prc_executed;

     int started=0;     //any process runs scheduling started 

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

           t_BRS[i] = BRS[i];

     while(remain)

     {

           prc_executed = 0;

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

           {

                //If process has arrived at this time

                //and has burst time remaining then run it.

                if(t_BRS[i] > 0 && ARR[i] <= exc_time)         

                {                                                         

                //If no process has started then no need for CONTEXT_SWT.

                //When schedular is idle started is set to 0, since it is now ruuning set stated to 1.

                //If some process was ruuninng in previous time quantum add CONTEXT_SWT.

                     if(started == 0)                               

                           started = 1;                              

                     else                                           

                           exc_time = exc_time + CONTEXT_SWT;

                    

                     //If first run

                     //then current exc_time is its start time.

                     if(STR[i] == -1)                               

                           STR[i] = exc_time;

                          

                     //Decrease TIME_QUANTUM from BRST time because process has run for this time.

                     t_BRS[i] = t_BRS[i] - TIME_QUANTUM;       

                     //Increase exc_time by TIME_QUANTUM.

                     exc_time = exc_time + TIME_QUANTUM;

                     //Mark that a process was executed, used to increment exc_time

                     //by 1 unit if no process was ready to run

                     prc_executed = 1;                              

                                                                          

                     if(t_BRS[i] <= 0)

                     {    //If process completes.

                           exc_time = exc_time + t_BRS[i];     

                           //If t_BRS[i] is -ve means it ran for less than TIME_QUANTUM and extra time must be subtracted.

                           //This extra time is in t_BRS[i],e.g, if it had to runs for 1s and TIME_QUANTUM is 3s then

                           //it should only run for 1s. so after t_BRS[i] = t_BRS[i] - TIME_QUANTUM, t_BRS[i] is -2, meanining

                           //2s must be subtracted from exc_time

                           FIN[i] = exc_time;         //current exc_time is finish time then

                           remain--;                  //decrease number of remaining process

                     }

                }

           }

          

           if(prc_executed == 0)

           {

                //If no process executed increment execution time by 1 unit, this is used in case there is no process ready to run.

                started = 0;

                //since no process was executed set schedular to idle so that there is no contect switch when a process arrives

                exc_time++;         

           }   

     }

}

void calc(int *tt, int *tw,float *at,float *aw)

{

     int i;

     *tw = *tt = 0;

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

     {

           TRN[i] = FIN[i] - ARR[i];            //turnaround time = finish time - submission time

           WAT[i] = TRN[i] - BRS[i];            //wait time = finish time - submission time - burst time

                                                //or wait time = turnaround time - burst time, this is time spent in ready queue

           *tw += WAT[i];

           *tt += TRN[i];       //total wait & turn around times

     }

     *at = (float)*tt/NUM_PRC;

     *aw = (float)*tw/NUM_PRC;       //average wait & turn around times

}

void print(int *tt, int *tw,float *at,float *aw)

{

     int i;

     printf("\n\nPID ARR BRS STR FIN WAT TRN");

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

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

           printf("\n%3d %3d %3d %3d %3d %3d %3d",i+1,ARR[i],BRS[i],STR[i],FIN[i],WAT[i],TRN[i]);

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

     printf("\nTOTAL TURNAROUND TIME : %d\tAVERAGE TURNAROUND TIME : %.2f",*tt,*at);

     printf("\nTOTAL WAITING    TIME : %d\tAVERAGE WAITING    TIME : %.2f",*tw,*aw);

}