Friday, July 1, 2011

EXPRESSION TREE program


#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;
}


Posted by at No comments:
Labels: , , , ,

INFIX to POSTFIX conversion


#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;
}


Posted by at No comments:
Labels: , , , ,
Subscribe to: Posts (Atom)