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;

}

Modify STACK EXAMPLE to create A DYNAMIC QUEUE

DYNAMIC QUEUE using DYNAMIC STACK

//TITLE         DYNAMIC QUEUE by modifying DYNAMIC STACK

//AUTHOR        VINAY CHOUDHARY

//DATE          26 OCT 2009

//This is a C program for DYNAMIC queue using stack functions

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#define NUM 5

/*

*pos  :    we will use "pos" to point to top element in array,            used in pop, value updates in push.

*arr  :    pointer to array which is allocated memory at run-time.Can be replaced by static array. Just comment out part where we are using malloc() for array in push().

num   :    "num" tells how much data is present.

*next :    "*next" is pointer to next stack element.

*/

typedef struct blk{

     int *pos;                 

     int *arr;                 

     int num;         

     struct blk *next;   

}stack;

/*

PUSH FUCTION : we pass head as pointer and data here. Head is stored in backup for returning new value when stack is created for first time, else it contains old head value.

In loop above we check if head exists and go to last stack,which has next == null. There we check if head(stack) exists or not or if array is full for current last stack. In both cases we create a new stack as temp. temp points to NULL, since it will be last stack and has no data at present so num = 0 for temp and make pos to point to base of arr.

Now if stack doesnt exist then assign temp as head of stack since we will add data to it. Also since this is new head, store it in backup for returning purpose, else if array has filled for current last stack attach newly created temp stack to stack by storing its address in next of curent stack and make head same as temp since we add data to newly created stack(temp) using head(head=temp).

Then add data and increment index and return backup

*/

stack* push(stack *head,int data)

{         

     stack* backup,*temp;                

     for(backup = head;head && head->next != NULL;head = head->next);               

     if(head == NULL || head->num == NUM)

     {              

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

           temp->arr = (int*)malloc(NUM*sizeof(int));

           temp->next = NULL;                                  

           temp->num = 0;      

           temp->pos = temp->arr;                              

           if(backup == NULL)

                backup = head = temp;

           else if(head->num == NUM)

                head = head->next = temp;

     }                                        

     head->arr[head->num++] = data

    

     return backup;

}

//POP FUNCTION: we pass head as pointer and data as pointer here.

//save backup as head;

//Read data at pos. pos is where queue starts

//since data at pos is read, now we will read next element next time so //pos++

//and take data in pointer passed, which is collected in main

//here we check if array of current last stack has become empty, if so

//second last stack, use temp to make second last stack to point to NULL. //Hence stack

//pointed by temp is now the last stack. Free memory of stack to be deleted.

//NOTE THAT stack is deleted only when no data is left

//whether updated or not return backup which is collected as head in main //program

stack* pop(stack *head,int *data)

{        

stack* backup,*temp=NULL;

     backup = head;                                 

     *data = *head->pos;       

     head->pos++;              

     --head->num;                   

if(head->num == 0)

{                    

temp = head->next;

           free(head->arr);    

           free(head);               

           backup = temp;           

}         

     return backup; 

}

void display(stack *head)

{   

     int *p,i;                                 

    

     printf("\nCURRENT STACK: ");

    

     if(!head)

           printf("DOESN'T EXIST");

    

     while(head)

{

           for(i=0,p=head->pos;i<head->num;p++,i++)

                printf("%d ",*p);

           head = head->next;

     }

}

void main()

{

     stack *head=NULL;

     int data,run=1;

     char ch;

     while(run)

{

           display(head);

           printf("\n\nWHAT TO DO ?");

           printf("\n1. PUSH\n2. POP\n3. DISPLAY\n4. EXIT\nYOUR OPTION : ");

           scanf(“%c”,&ch);

           switch(ch)

{

                case '1':

{

                     printf("Enter number to push: ");

                     scanf(“%d”,&data);

                     head = push(head,data);        

                     break;

                }

    

                case '2':

{                                         

                     if( (head) )

{                              

                           head = pop(head,&data);   

                           printf("DATA POPPED: %d",data);

                          

                     }

                     else

                           printf("CAN'T POP: NO DATA IN STACK");

                     break;

                }

    

                case '3':

{

                     display(head);

                     break;

                }

                case '4':

{

                     run = 0;

                     break;

                }

               

                default:

{

                     printf("\nENTER VALID OPTION");

                     break;

                }

           }

     }

     printf("\n\n");

}

A STACK PROGRAM EXAMPLE.

PROBLEM : we must create a stack using linked list with following specifications:
1. USING LINKED LIST
2. DYNAMIC IN SIZE
3. EACH STACK NODE CONTAINS AN ARRAY OF N(=5 in code) SIZE.

SAMPLE DIAGRAM

The code is shown below:

//TITLE         DYNAMIC STACK

//AUTHOR        VINAY CHOUDHARY

//DATE          26 OCT 2009

//This is a C program for DYNAMIC STACK

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#define NUM 5

//pointer to array which is allocated memory at run-time. Can be //replaced by static

//array. Just comment out part where we are using malloc() for array //in push(). "num"

//tells how much data is present. "*next" is pointer to next stack

typedef struct blk

{

     int *arr;                 

     int num;                  

     struct blk *next;         

}stack;

//PUSH FUCTION : we pass head as pointer and data here.

//head is stored in backup for returning new value when

//stack is created for first time, else it contains old head value.

//In for loop we check if head exists and go to last stack,which has //next == null

//here we check if head(stack) exists or not or if array is

//full for current last stack. In both cases we create a new stack

//as temp. temp points to NULL, since it will be last stack

//and has no data at present so num = 0 for temp.

//now if stack doesnt exist then assign temp as head of stack since //we will add data to it. Also since this is new head store it in //backup for returning purpose,else if array has filled for current //last stack attach newly created temp stack to stack by storing its //address in next of curent stack and make head same as temp since //we add data to newly created stack(temp) using head(head=temp)

//add data

//and increment index. THIS INDEX CAN BE USED AS STACK POINTER

stack* push(stack *head,int data)

{         

     stack* backup,*temp;                

                                                    

     for(backup = head;head && head->next != NULL;head = head->next);               

    

     if(head == NULL || head->num == NUM){          

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

           temp->arr = (int*)malloc(NUM*sizeof(int));

           temp->next = NULL;                                  

           temp->num = 0; 

           if(backup == NULL)             

                backup = head = temp;

           else if(head->num == NUM)      

                head = head->next = temp; 

     }                                              

     head->arr[head->num] = data;   

     head->num = head->num + 1;     

     return backup;

}

//POP FUNCTION: we pass head as pointer and data as pointer here.

//temp will have first stack if there is only one stack else it //stores second last stack address

//in loop above we intialise temp = head and go to last stack //structure.

//decrement index. THIS INDEX CAN BE USED AS STACK POINTER

//and take data in pointer passed, which is collected in main.

//here we check if array of current last stack has become empty, if //so we need to delete it. But if there was only one stack (then //temp == head), make backup point to NULL and return it later, //since existing stack will //be removed.

//if there were more than one stacks, then delete last one. Since //temp has address of

//second last stack, use temp to make second last stack to point to //NULL. Hence stack pointed by temp is now the last stack. Free //memory of stack to be deleted.

stack* pop(stack *head,int *data)

{   

     stack* backup=NULL,*temp=NULL;

    

     for(backup = head,temp = head;head->next != NULL;temp = head,head = head->next);

    

     head->num = head->num - 1;     

     *data = head->arr[head->num];  

     if(head->num == 0)

{         

           if(temp == head)    

                backup = NULL; 

           temp->next=NULL;    

           free(head->arr);    

           free(head);               

     }

     return backup;

}

void display(stack *head)

{

     int i;

    

     printf("\nCURRENT STACK: ");

    

     if(!head)

           printf("DOESN'T EXIST");

    

     while(head)

{

           for(i=0;i<head->num;i++)

                printf("%d ",head->arr[i]);

           head = head->next;

     }

}

void main()

{

     stack *head=NULL;

     int data,run=1,cls=0;

     char ch;

     while(run)

{

           display(head);

           printf("\n\nWHAT TO DO ?");

           printf("\n1. PUSH\n2. POP\n3. DISPLAY\n4. EXIT\nYOUR OPTION : ");

           scanf(“%c”,&ch);

           switch(ch)

{

                case '1':{

                     printf("Enter number to push: ");

                     scanf(“%d”,&data);

                     head = push(head,data);        

                     break;

                }

    

                case '2':{                                

                     if( (head) )

{                              

                           head = pop(head,&data);   

                           printf("DATA POPPED: %d",data);

                     }

                     else

                           printf("CAN'T POP: NO DATA IN STACK");

                     break;

                }

    

                case '3':{

                     display(head);

                     break;

                }

                case '4':{

                     run = 0;

                     break;

                }

               

                default:{

                     system("cls");

                     printf("\nENTER VALID OPTION");

                     break;

                }

           }

     }

     printf("\n\n\);

}