Program to convert expression infix to prefix

//infix to prefix

#include<stdio.h>

#include<string.h>

#define SIZE 10

int pr(char op)
{
if(op=='*' || op=='/')
return 3;
if(op=='+' || op=='-')
return 2;
else
return 0;
}

char stack[SIZE];
int top=-1;

void push(char op)
{
stack[++top]=op;
}

char pop()
{
return stack[top--];
}

void polish(char infix[],char prefix[])
{
int i,l,j=0;
char op;
strrev(infix);
l=strlen(infix);
infix[l]='(';
infix[l+1]='\0';
push(')');
for(i=0;infix[i]!='\0';i++)
{
if(isalpha(infix[i]))
{
prefix[j++]=infix[i];
continue;
}
if(infix[i]==')')
{
push(infix[i]);
continue;
}
if(infix[i]=='(')
{
while((op=pop())!=')')
prefix[j++]=op;
}
else
{
while(pr(infix[i])<pr(stack[top]))
prefix[j++]=pop();
push(infix[i]);
}

}
prefix[j]='\0';
strrev(prefix);
}

int main()
{
char infix[20],prefix[20];
printf("\nEnter the infix : ");
gets(infix);
polish(infix,prefix);
printf("\nprefix : %s",prefix);

return 0;
}

Program to convert express infix to postfix in stack using array

//infix to postfix





#include<stdio.h>

#include<string.h>

#define SIZE 10

int pr(char op)
{
if(op=='*' || op=='/')
return 3;
if(op=='+' || op=='-')
return 2;
else
return 0;
}

char stack[SIZE];
int top=-1;

void push(char op)
{
stack[++top]=op;
}

char pop()
{
return stack[top--];
}

void rev_polish(char infix[],char postfix[])
{
int i,l,j=0;
char op;
l=strlen(infix);
infix[l]=')';
infix[l+1]='\0';
push('(');
for(i=0;infix[i]!='\0';i++)
{
if(isalpha(infix[i]))
{
postfix[j++]=infix[i];
continue;
}
if(infix[i]=='(')
{
push(infix[i]);
continue;
}
if(infix[i]==')')
{
while((op=pop())!='(')
postfix[j++]=op;
}
else
{
while(pr(infix[i])<=pr(stack[top]))
postfix[j++]=pop();
push(infix[i]);
}

}
postfix[j]='\0';
}

int main()
{
char infix[20],postfix[20];
printf("\nEnter the infix : ");
gets(infix);
rev_polish(infix,postfix);
printf("\nPostfix : %s",postfix);
return 0;
}

circular queue using linked list

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<stdlib.h>

#define SIZE 5

int Q[SIZE],front=-1,rear=-1;

void insert(int x)
{
if( (front==0 && rear==SIZE-1) || front==rear+1)
{
printf("\nOverflow");
return ;
}
if(rear==-1)
front=rear=0;
else
if(rear==SIZE-1)
rear=0;
else
rear++;
Q[rear]=x;
}

int del()
{
int item;
if(front==-1)
{
printf("\nUnderflow");
return -9999;
}
item=Q[front];
if(front==rear)
front=rear=-1;
else
if(front==SIZE-1)
front=0;
else
front++;
return item;
}

int main()
{
int n,ch;
while(1)
{
printf("\n\t\t\tMenu");
printf("\n\t\t\t1 : Insert");
printf("\n\t\t\t2 : Deletion");
printf("\n\t\t\t3 : Exit");
printf("\n\t\t\tEnter your choice :");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\nEnter the item :");
scanf("%d",&n);
insert(n);
break;
case 2:
n=del();
if(n!=-9999)
printf("\nPopped item : %d",n);
break;
case 3:
exit(0);
default:
printf("\nInvalid Choice");
}
}
return 0;
}

priority queue using linked list

//priority queue using linked list

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

typedef struct node
{
int info,pr;
struct node *next;
}node;
node *start=NULL;

void insert_at_end(int x,int p);
void insert_at_beg(int x,int p);
void insert_at_specific(int ,int, int);
void del_at_beg();
void insert(int x,int p);

int main()
{
int n,po,ch,p;
while(1)
{
printf("\n\t\t\tMenu");
printf("\n\t\t\t1 : Insertion");
printf("\n\t\t\t2 : Deletion");
printf("\n\t\t\t3 : Exit");
printf("\n\t\t\tEnter ur choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\nEnter the info :");
scanf("%d",&n);
printf("\nEnter the priority :");
scanf("%d",&p);
insert(n,p);
break;
case 2:
del_at_beg();
break;
case 3:
exit(0);
default:
printf("\nInvalid choice");
}
}
return 0;
}

void insert_at_end(int x, int p)
{
node *temp,*new_node;
new_node=(node*)malloc(sizeof(node));
new_node->info=x;
new_node->pr=p;
new_node->next=NULL;
if(start==NULL)
start=new_node;
else
{
temp=start;
while(temp->next!=NULL)
temp=temp->next;
temp->next=new_node;
}
}

void insert_at_beg(int x,int p)
{
node *new_node;
new_node=(node*)malloc(sizeof(node));
new_node->info=x;
new_node->pr=p;
new_node->next=start;
start=new_node;
}

void insert_at_specific(int x,int p,int po)
{
int i;
node *new_node,*temp;
if(po<1 || po>count()+1)
{
printf("\nInvalid position");
return;
}
if(po==1)
insert_at_beg(x,p);
else
{
if(po==count()+1)
insert_at_end(x,p);
else
{
new_node=(node*)malloc(sizeof(node));
new_node->info=x;
new_node->pr=p;
new_node->next=NULL;
temp=start;
for(i=1;i<po-1;i++)
temp=temp->next;
new_node->next=temp->next;
temp->next=new_node;
}
}
}


int count()
{
node *temp;
int c=0;
for(temp=start;temp!=NULL;temp=temp->next)
c++;
return c;
}

void del_at_beg()
{
node *temp;
if(start==NULL)
{
printf("\nList Empty");
return;
}
temp=start;
start=start->next;
printf("\nDeleted node : %d",temp->info);
printf("\nDeleted priority : %d",temp->pr);
free(temp);
}

void insert(int x,int p)
{
node *temp;
int po=0;
if(start==NULL)
{
insert_at_beg(x,p);
return;
}
temp=start;
while(temp!=NULL)
{
if(temp->pr >= p)
{
po++;
temp=temp->next;
}
else
break;
}
insert_at_specific(x,p,po+1);
}

implemention of linked list(add at beg,add at end, add at specific position, delete at beg, delete at end, delete at specific postion )

//add_at_beg, add_at_end,add_at_specific,del_at_beg, del_at_end,del_at_specific

#include<stdio.h>

#include<conio.h>
#include<malloc.h>

typedef struct node
{
int info;
struct node *next;
}node;
node *start=NULL;

void insert_at_end(int x);
void insert_at_beg(int x);
void insert_at_specific(int ,int);
void disp();
void del_at_beg();
void del_at_end();
void del_at_specific(int po);
int seq_search(int item);
void sort();

int main()
{
int n,po,ch;
while(1)
{
printf("\n\t\t\tMenu");
printf("\n\t\t\t1 : Insertion at end");
printf("\n\t\t\t2 : Insertion at beg");
printf("\n\t\t\t3 : Insertion at specific");
printf("\n\t\t\t4 : Display");
printf("\n\t\t\t5 : Deletion at beg");
printf("\n\t\t\t6 : Deletion at end");
printf("\n\t\t\t7 : Deletion at specific");
printf("\n\t\t\t8 : Search");
printf("\n\t\t\t9 : Sorting");
printf("\n\t\t\t10 : Exit");
printf("\n\t\t\tEnter ur choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\nEnter the info :");
scanf("%d",&n);
insert_at_end(n);
break;
case 2:
printf("\nEnter the info :");
scanf("%d",&n);
insert_at_beg(n);
break;
case 3:
printf("\nEnter the position :");
scanf("%d",&po);
printf("\nEnter the info :");
scanf("%d",&n);
insert_at_specific(n,po);
break;
case 4:
disp();
break;
case 5:
del_at_beg();
break;
case 6:
del_at_end();
break;
case 7:
printf("\nEnter the position :");
scanf("%d",&po);
del_at_specific(po);
break;
case 8:
printf("\nEnter the item :");
scanf("%d",&n);
po=seq_search(n);
if(po!=-1)
printf("\nFound at %d",po);
else
printf("\nNot Found.");
break;
case 9:
sort();
break;
case 10:
exit(0);
default:
printf("\nInvalid choice");
}
}
return 0;
}

void insert_at_end(int x)
{
node *temp,*new_node;
new_node=(node*)malloc(sizeof(node));
new_node->info=x;
new_node->next=NULL;
if(start==NULL)
start=new_node;
else
{
temp=start;
while(temp->next!=NULL)
temp=temp->next;
temp->next=new_node;
}
}

void insert_at_beg(int x)
{
node *new_node;
new_node=(node*)malloc(sizeof(node));
new_node->info=x;
new_node->next=start;
start=new_node;
}

void insert_at_specific(int x,int po)
{
int i;
node *new_node,*temp;
if(po<1 || po>count()+1)
{
printf("\nInvalid position");
return;
}
if(po==1)
insert_at_beg(x);
else
{
if(po==count()+1)
insert_at_end(x);
else
{
new_node=(node*)malloc(sizeof(node));
new_node->info=x;
new_node->next=NULL;
temp=start;
for(i=1;i<po-1;i++)
temp=temp->next;
new_node->next=temp->next;
temp->next=new_node;
}
}
}

void disp()
{
node *temp;
printf("\nElements in the list are : ");
for(temp=start;temp!=NULL;temp=temp->next)
printf("%d ",temp->info);
}

int count()
{
node *temp;
int c=0;
for(temp=start;temp!=NULL;temp=temp->next)
c++;
return c;
}

void del_at_beg()
{
node *temp;
if(start==NULL)
{
printf("\nList Empty");
return;
}
temp=start;
start=start->next;
printf("\nDeleted node is %d",temp->info);
free(temp);
}

void del_at_end()
{
node *temp;
int i;
if(start==NULL)
{
printf("\nList Empty");
return;
}
if(count()==1)
{
del_at_beg();
return;
}
temp=start;
for(i=1;i<count()-1;i++)
temp=temp->next;
printf("\nDeleted node is %d",temp->next->info);
free(temp->next);
temp->next=NULL;
}

void del_at_specific(int po)
{
int i;
node *temp,*temp1;
temp=start;
for(i=1;i<po-1;i++)
temp=temp->next;
temp1=temp->next;
temp->next=temp1->next;
printf("\nDeleted node is %d",temp->info);
free(temp1);
}

int seq_search(int item)
{
int po=0;
node *temp;
temp=start;
while(temp!=NULL)
{
po++;
if(temp->info==item)
return po;
temp=temp->next;
}
return -1;
}


void sort()
{
int t;
node *i,*j;
for(i=start;i!=NULL;i=i->next)
{
for(j=i->next;j!=NULL;j=j->next)
{
if(i->info > j->info)
{
t=i->info;
i->info=j->info;
j->info=t;
}
}
}
}

merge two linked list

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

typedef struct node
{
int info;
struct node *next;
}node;

node *start1=NULL,*start2=NULL,*start3=NULL,*cur;

void make_node(int x)
{
cur=(node*)malloc(sizeof(node)) ;
cur->info=x;
cur->next=NULL;
}
void create_list(node **first, int x)
{
node *temp;
make_node(x);
if(*first==NULL)
*first=cur;
else
{
temp=*first;
while(temp->next!=NULL)
temp=temp->next;
temp->next=cur;
}
}
void traverse(node *first)
{
while(first!=NULL)
{
printf("\t%d",first->info);
first=first->next;
}
}
void sort(node *first)
{
node *n;
int temp;
for(;first!=NULL;first=first->next)
{
for(n=first->next;n!=NULL;n=n->next)
{
if(first->info > n->info)
{
temp=first->info;
first->info=n->info;
n->info=temp;
}
}
}
}

void merge()
{
node *m,*n;
m=start1;
n=start2;
while(m!=NULL && n!=NULL)
{
if(m->info < n->info)
{
create_list(&start3,m->info);
m=m->next;
}
else
{
create_list(&start3,n->info);
n=n->next;
}
}
while(m!=NULL)
{
create_list(&start3,m->info);
m=m->next;
}
while(n!=NULL)
{
create_list(&start3,n->info);
n=n->next;
}
}

int main()
{
int n;
char ch;
printf("\nCreate the first list :\n");
do
{
printf("\nEnter the info :");
scanf("%d",&n);
create_list(&start1,n);
printf("\nWant to continue?[y/n] :");
ch=getche();
}while(toupper(ch)=='Y');
printf("\nCreate the second list :\n");
do
{
printf("\nEnter the info :");
scanf("%d",&n);
create_list(&start2,n);
printf("\nWant to continue?[y/n] :");
ch=getche();
}while(toupper(ch)=='Y');
printf("\n\nFirst List :");
traverse(start1);
printf("\n\nSecond List :");
traverse(start2);
sort(start1);
sort(start2);
merge();
printf("\n\nMerged List :");
traverse(start3);
getch();
return 0;
}