priority queue

#include<stdio.h>

#include<conio.h>

#define MAX 5

struct queue

{

      int a[5];

      int rear,front;

}

st;

void enqueue(int x);

void dequeue();

void display();

void main()

{

      int op,x;

      st.rear=st.front=-1;

      do

      {

            printf("n1.Insertion\n2.Deletion\n3.Print\n4.Exit");

            printf("\nEnter choice=");

            scanf("%d",&op);

            switch(op)

            {

                  case 1:if((st.rear+1)%MAX==st.front)

                  printf("\nQueue is full");

                  else

                  enqueue(x);

                  break;

                  case 2:if(st.front==-1)

                  printf("\nEmpty queue");

                  else

                  {

                        dequeue();

                  }

                  break;

                  case 3:display();

                  break;

            }

      }while(op!=4);

      getch();

}

void enqueue(int x)

{

      int i;

      printf("\nEnter data:");

      scanf("%d",&x);

      if(st.rear==-1)

      {

            st.rear++;

            st.front++;

            st.a[st.rear]=x;

      }

      else

      {

            i=st.rear;

            while(x>st.a[i])

            {

                  st.a[(i+1)%MAX]=st.a[i];

                  i=(i-1+MAX)%MAX;

                  if((i-1)%MAX==st.front)

                  break;

            }

            i=(i+1)%MAX;

            st.a[i]=x;

            st.rear=(st.rear+1)%MAX;

      }

}

void dequeue()

{

      int y;

      if(st.rear==st.front)

      {

            y=st.a[st.front];

            st.front=-1;

            st.rear=-1;

      }

      else

      {

            y=st.a[st.front];

            st.front=(st.front+1)%MAX;

      }

      printf("\nDeleted element=%d",y);

}

void display()

{

      int i;

      if(st.rear==-1)

      printf("\nEmpty queue");

      else

      {

            printf("\nQueue is:");

            i=st.front;

            while(i!=st.rear)

            {

                  printf("<%d>",st.a[i]);

                  i=(i+1)%MAX;

            }

            printf("<%d>",st.a[st.rear]);

      }

}

                  

program to covert prefix to postfix

#include<stdio.h>

#include<conio.h>

#include<ctype.h>

#define MAX 30

char stack[MAX][MAX];

int top;

void pre_to_post(char prefix[],char postfix[]);

void convert_postfix(char x);

main()

{

      char prefix[30],postfix[30];

      printf("Enter prefix=");

      gets(prefix);

      pre_to_post(prefix,postfix);

      printf("The postfix expression is=");

      puts(postfix);

      getch();

}

void pre_to_post(char prefix[30],char postfix[30])

{

      int top=-1,i,n;

      char x,st1[30];

      n=strlen(prefix);

      for(i=n-1;i>=0;i--)

      {

            x=prefix[i];

            if(isalnum(x))

            {

                  st1[0]=x;

                  st1[1]='\0';

                  top++;

                  strcpy(stack[top],st1);

            }

            else

            {

                  convert_postfix(x);

            }

      }

      strcpy(postfix,stack[top]);

}

void convert_postfix(char x)

{

      char st1[30],st2[30];

      st2[0]=x;

                  st2[1]='\0';

                  strcpy(st1,stack[top]);

                  strcat(st1,stack[top-1]);

                  strcat(st1,st2);

                  top=top-1;

                  strcpy(stack[top],st1);

}

      

program to evaluate a prefix expression using stack

.

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

main()

{

      char s[80];

      int stack[80],n,top=-1,x=0,y=0,i;

      printf("Enter postfix expression=");

      gets(s);

      n=strlen(s);

      for(i=n;i>=0;i--)

      {

            switch(s[i])

            {

                  case '+':

                  x=stack[top];

                  y=stack[top-1];

                  top=top-1;

                  x=x+y;

                  stack[top]=x;

                  break;

                  case '-':

                  x=stack[top];

                  y=stack[top-1];

                  top=top-1;

                  x=x-y;

                  stack[top]=x;

                  break;

                  case '*':

                  x=stack[top];

                  y=stack[top-1];

                  top=top-1;

                  x=x*y;

                  stack[top]=x;

                  break;

                  case '/':

                  x=stack[top];

                  y=stack[top-1];

                  top=top-1;

                  x=x/y;

                  stack[top]=x;

                  break;

                  default:

                  top=top++;

                  if(s[i]>=48&&s[i]<=57)

                  x=s[i]-48;

                  stack[top]=x;

                  break;

            }

      }

      printf("The result is=%d",stack[top]);

      getch();

}

program to convert prefix to infix

#include<stdio.h>

#include<conio.h>

#include<string.h>

#include<ctype.h>

#define MAX 20

void convert_infix(char x);

void pretoin(char prefix[],char infix[]);

char stack[MAX][MAX];

int top=-1;

void main()

{

char prefix[30],infix[30];

//clrscr();

printf("\nEnter prefix=");

gets(prefix);

pretoin(prefix,infix);

printf("infix expression : %s",infix);

getch();

}

void pretoin(char prefix[],char infix[])

{

int i,top=-1;

char x,st1[30];

for(i=strlen(prefix)-1;i>=0;i--)

{

x=prefix[i];

if(isalnum(x))

{

st1[0]=x;

st1[1]='\0';

top=top+1;

strcpy(stack[top],st1);

}

else

{

convert_infix(x);

}

}

strcpy(infix,stack[top]);

}

void convert_infix(char x)

{

      char st1[30],st2[30];

      st1[0]='(';

st1[1]='\0';

strcat(st1,stack[top]);

st2[0]=x;

st2[1]='\0';

strcat(st1,st2);

strcat(st1,stack[top-1]);

st2[0]=')';

st2[1]='\0';

strcat(st1,st2);

top=top-1;

strcpy(stack[top],st1);

}

Prpgram to convert postfix to prefix expression.

#include<stdio.h>

#include<conio.h>

#include<ctype.h>

#include<string.h>

#define MAX 20

char stack[MAX][MAX];

int top;

void posttopre(char post[30],char prefix[30])

{

      int top=-1,i;

      char x,st1[30];

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

      {

            x=post[i];

            if(isalnum(x))

            {

                  st1[0]=x;

                  st1[1]=NULL;

                  top=top+1;

                  strcpy(stack[top],st1);

            }

            else

            {

                  st1[0]=x;

                  st1[1]=NULL;

                  strcat(st1,stack(top-1));

                  strcat(st1,stack(top));

                  top=top-1;

                  strcpy(stack[top],st1);

            }

      }

}

main()

{

      char post[30],prefix[30];

      char x;

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

      gets(post);

      posttopre(post,prefix);

      strcpy(prefix,stack[top]);

      printf("\n\nThe prefix expression is= %s",prefix);

      getch();

}

program to evaluate postfix expression using atack.

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

main()

{

      char s[80];

      int stack[80],n,top=-1,x=0,y=0,i;

      printf("Enter postfix expression=");

      gets(s);

      n=strlen(s);

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

      {

            switch(s[i])

            {

                  case '+':

                  y=stack[top];

                  x=stack[top-1];

                  top=top-1;

                  x=x+y;

                  stack[top]=x;

                  break;

                  case '-':

                  y=stack[top];

                  x=stack[top-1];

                  top=top-1;

                  x=x-y;

                  stack[top]=x;

                  break;

                  case '*':

                  y=stack[top];

                  x=stack[top-1];

                  top=top-1;

                  x=x*y;

                  stack[top]=x;

                  break;

                  case '/':

                  y=stack[top];

                  x=stack[top-1];

                  top=top-1;

                  x=x/y;

                  stack[top]=x;

                  break;

                  default:

                  top=top++;

                  if(s[i]>=48&&s[i]<=57)

                  x=s[i]-48;

                  stack[top]=x;

                  x=0;

                  break;

            }

      }

      printf("The result is=%d",stack[top]);

      getch();

}

program to implement merge sort.

#include<stdio.h>

#define MAX 50

void mergeSort(int arr[],int low,int mid,int high);

void partition(int arr[],int low,int high);

int main()

{

int merge[MAX],i,n;

printf("Enter the total number of elements: ");

scanf("%d",&n);

printf("Enter the elements which to be sort: ");

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

{

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

}

partition(merge,0,n-1);

printf("After merge sorting elements are: ");

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

{

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

}

return 0;

}

void partition(int arr[],int low,int high)

{

int mid;

if(low<high)

{

mid=(low+high)/2;

partition(arr,low,mid);

partition(arr,mid+1,high);

mergeSort(arr,low,mid,high);

}

}

void mergeSort(int arr[],int low,int mid,int high)

{

int i,m,k,l,temp[MAX];

l=low;

i=low;

m=mid+1;

while((l<=mid)&&(m<=high))

{

if(arr[l]<=arr[m])

{

temp[i]=arr[l];

l++;

}

else

{

temp[i]=arr[m];

m++;

}

i++;

}

if(l>mid)

{

for(k=m;k<=high;k++)

{

temp[i]=arr[k];

i++;

}

}

else

{

for(k=l;k<=mid;k++)

{

temp[i]=arr[k];

i++;

}

}

for(k=low;k<=high;k++)

{

arr[k]=temp[k];

}

}

Program to invert elements of a singly linked list.

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

typedef struct node

{

      int data;

      struct node *next;

}node;

main()

{

      node *head,*p,*q,*r;

      int n,i,j;

      printf("N=");

      scanf("%d",&n);

      head=(node *)malloc(sizeof(node));

      scanf("%d",&head->data);

      p=head;

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

      {

            p->next=(node *)malloc(sizeof(node));

            p=p->next;

            scanf("%d",&p->data);

            p->next=NULL;

      }

      p=head;

      printf("\n\nThe linked list 1 is=\n\nHead");

      while(p!=NULL)

      {

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

            p=p->next;

      }

      p=NULL;

      q=head;

      //r=q->next;

      printf("\n\nThe inversed linked list is=\n\nHead");

      while(q!=NULL)

      {

            r=p;

            p=q;

            q=q->next;

            p->next=r;

      }

      head=p;

      while(p!=NULL)

      {

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

            p=p->next;

      }

      getch();

}

     

      

program for covert infix to postfix

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

struct stack

{

      char s[30];

      int top;

}st;

main()

{

      char infix[30],postfix[30];

      void intopost(char infix[30]);

      printf("Enter expression=");

      gets(infix);

      intopost(infix);

      //printf("\n\nThe postfix expression is=");

      //puts(postfix);

      getch();

}

void intopost(char infix[30])

{

      int i,j;

      char postfix[30];

      char ch;

      int incoming(char ch);

      int instack(char ch);

      void push(char item);

      char pop();

      st.top=-1;

      st.top=st.top++;

      st.s[st.top]='$';

      j=0;

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

      {

            ch=infix[i];

            while(instack(st.s[st.top])>incoming(ch))

            {

                  postfix[j]=pop();

                  j++;

            }

            if(instack(st.s[st.top])!=incoming(ch))

            push(ch);

            else

            pop();

      }

      while(ch=pop()!='$')

      {

            postfix[j]=ch;

            j++;

      }

      postfix[i]='\0';

      printf("\n\nThe postfix expression is=%s",postfix);

}

int instack(char ch)

{

      int priority;

      switch(ch)

      {

            case '+':

            case '-':

            priority=2;

            break;

      case '*':

            case '/':

            priority=4;

            break;

            case '^':

            priority=5;

            break;

            case '(':

            priority=0;

            break;

            case '$':

            priority=-1;

            break;

      default:

            priority=8;

      }

      return(priority);

}

int incoming(char ch)

{

      int priority;

      switch(ch)

      {

            case '+':

            case '-':

            priority=1;

            break;

      case '*':

            case '/':

            priority=3;

            break;

            case '^':

            priority=6;

            break;

            case '(':

            priority=9;

            break;

            case '$':

            priority=0;

            break;

      default:

            priority=7;

      }

      return(priority);

}

void push(char item)

{

      st.top++;

      st.s[st.top]=item;

}

char pop()

{

      char e;

      e=st.s[st.top];

      st.top--;

      return e;

}

Program to implement insertion sort.

#include<stdio.h>

int main()

{

int i,j,s,temp,a[20];

printf("Enter total elements: ");

scanf("%d",&s);

printf("Enter %d elements: ",s);

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

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

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

{

      temp=a[i];

      j=i-1;

      while((temp<a[j])&&(j>=0)){

      a[j+1]=a[j];

          j=j-1;

      }

      a[j+1]=temp;

  }

printf("After sorting: ");

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

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

return 0;

}

Program to convert infix to postfix expression.

#include<stdio.h>

#include<conio.h>         

#include <ctype.h>

#define SIZE 50

char s[SIZE];

int top=-1;     

push(char c)

{                      

    s[++top]=c;

}

char pop()

{                      

    return(s[top--]);

}

int priority(char c)

{                

    switch(c){

    case '$':

      return 0;

    case '(':

      return 1;

    case '+':

    case '-':

      return 2;

    case '*':

    case '/':

      return 3;

    case '^':

      return 4;}

}

main()

{                        

char infix[50],postfix[50],ch,c;

    int i=0,j=0;

    printf("\nEnter the infix expression=\t");

    scanf("%s",infix);

    push('$');

    while((ch=infix[i++])!='\0')

    {

        if(ch =='(')

            push(ch);

        else if(isalnum(ch))

            postfix[j++]=ch;

            else if( ch ==')'){

            while(s[top] !='(')

                  postfix[j++]=pop();

                    c=pop();

                              }

        else{      

        while(priority(s[top])>=priority(ch))

        postfix[j++]=pop();

        push(ch);

        }

    }

    while( s[top] != '$')    

    postfix[j++]=pop();

    postfix[j]='\0';        

    printf("\n\nThe Postfix Expn: %s\n",postfix);

    getch();

}