TREE

Posted Date: 16 Jan 2008 Resource Type: Articles/Knowledge Sharing Category: Computer & Technology

Posted By: Sagaya James Immanuel Member Level: Bronze
Rating:

Points: 3

1) /* Array to binary Tree */
/* Program to build a binary search tree from an array. */

#include
#include
#include

struct node
{
struct node *left ;
char data ;
struct node *right ;
} ;

struct node * buildtree ( int ) ;
void inorder ( struct node * ) ;

char a[ ] = {
'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H', '\0',
'\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0'
} ;

void main( )
{
struct node *root ;

clrscr( ) ;

root = buildtree ( 0 ) ;
printf ( "In-order Traversal:\n" ) ;
inorder ( root ) ;

getch( ) ;
}
struct node * buildtree ( int n )
{
struct node *temp = NULL ;
if ( a[n] != '\0' )
{
temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
temp -> left = buildtree ( 2 * n + 1 ) ;
temp -> data = a[n] ;
temp -> right = buildtree ( 2 * n + 2 ) ;
}
return temp ;
}

void inorder ( struct node *root )
{
if ( root != NULL )
{
inorder ( root -> left ) ;
printf ( "%c\t", root -> data ) ;
inorder ( root -> right ) ;
}
}

--------------------------------------------------------------------------------

2) /* Insertion and deletion in binary tree */
/* Program to insert and delete a node
from the binary search tree. */

#include
#include
#include

#define TRUE 1
#define FALSE 0

struct btreenode
{
struct btreenode *leftchild ;
int data ;
struct btreenode *rightchild ;
} ;

void insert ( struct btreenode **, int ) ;
void delete ( struct btreenode **, int ) ;
void search ( struct btreenode **, int, struct btreenode **,
struct btreenode **, int * ) ;
void inorder ( struct btreenode * ) ;

void main( )
{
struct btreenode *bt ;
int req, i = 0, num, a[ ] = { 11, 9, 13, 8, 10, 12, 14, 15, 7 } ;

bt = NULL ; /* empty tree */

clrscr( ) ;

while ( i <= 8 )
{
insert ( &bt, a[i] ) ;
i++ ;
}
clrscr( ) ;
printf ( "Binary tree before deletion:\n" ) ;
inorder ( bt ) ;

delete ( &bt, 10 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;

delete ( &bt, 14 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;

delete ( &bt, 8 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;

delete ( &bt, 13 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;
}

/* inserts a new node in a binary search tree */
void insert ( struct btreenode **sr, int num )
{
if ( *sr == NULL )
{
*sr = malloc ( sizeof ( struct btreenode ) ) ;

( *sr ) -> leftchild = NULL ;
( *sr ) -> data = num ;
( *sr ) -> rightchild = NULL ;
}
else /* search the node to which new node will be attached */
{
/* if new data is less, traverse to left */
if ( num < ( *sr ) -> data )
insert ( &( ( *sr ) -> leftchild ), num ) ;
else
/* else traverse to right */
insert ( &( ( *sr ) -> rightchild ), num ) ;
}
}

/* deletes a node from the binary search tree */
void delete ( struct btreenode **root, int num )
{
int found ;
struct btreenode *parent, *x, *xsucc ;

/* if tree is empty */
if ( *root == NULL )
{
printf ( "\nTree is empty" ) ;
return ;
}

parent = x = NULL ;

/* call to search function to find the node to be deleted */
search ( root, num, &parent, &x, &found ) ;

/* if the node to deleted is not found */
if ( found == FALSE )
{
printf ( "\nData to be deleted, not found" ) ;
return ;
}

/* if the node to be deleted has two children */
if ( x -> leftchild != NULL && x -> rightchild != NULL )
{
parent = x ;
xsucc = x -> rightchild ;

while ( xsucc -> leftchild != NULL )
{
parent = xsucc ;
xsucc = xsucc -> leftchild ;
}

x -> data = xsucc -> data ;
x = xsucc ;
}

/* if the node to be deleted has no child */
if ( x -> leftchild == NULL && x -> rightchild == NULL )
{
if ( parent -> rightchild == x )
parent -> rightchild = NULL ;
else
parent -> leftchild = NULL ;

free ( x ) ;
return ;
}

/* if the node to be deleted has only rightchild */
if ( x -> leftchild == NULL && x -> rightchild != NULL )
{
if ( parent -> leftchild == x )
parent -> leftchild = x -> rightchild ;
else
parent -> rightchild = x -> rightchild ;

free ( x ) ;
return ;
}

/* if the node to be deleted has only left child */
if ( x -> leftchild != NULL && x -> rightchild == NULL )
{
if ( parent -> leftchild == x )
parent -> leftchild = x -> leftchild ;
else
parent -> rightchild = x -> leftchild ;

free ( x ) ;
return ;
}
}

/*returns the address of the node to be deleted, address of its parent and
whether the node is found or not */
void search ( struct btreenode **root, int num, struct btreenode **par, struct
btreenode **x, int *found )
{
struct btreenode *q ;

q = *root ;
*found = FALSE ;
*par = NULL ;

while ( q != NULL )
{
/* if the node to be deleted is found */
if ( q -> data == num )
{
*found = TRUE ;
*x = q ;
return ;
}

*par = q ;

if ( q -> data > num )
q = q -> leftchild ;
else
q = q -> rightchild ;
}
}

/* traverse a binary search tree in a LDR (Left-Data-Right) fashion */
void inorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
inorder ( sr -> leftchild ) ;

/* print the data of the node whose leftchild is NULL or the path has
already been traversed */
printf ( "%d\t", sr -> data ) ;

inorder ( sr -> rightchild ) ;
}
}

--------------------------------------------------------------------------------

3) /* Tree traversal(with search) */
#include
#include
struct node
{
int info;
struct node *llink;
struct node *rlink;
};

typedef struct node *NODE;

NODE getnode()
{
NODE x;
x = (NODE) malloc(sizeof(struct node));
if (x == NULL)
{
printf("Out of Memory");
exit(0);
}
return x;
}

void freenode (NODE x)
{
free(x);
}

NODE insert(int item, NODE root)
{
NODE temp;
NODE cur;
NODE prev;
char direction[10];
int i;

temp = getnode();
temp->info = item;
temp->llink = temp->rlink = NULL;

if (root == NULL)
return temp;

printf("Press [L] for Left insertion [R] for Right insertion\n");
fflush(stdin);
scanf("%s", direction);
toupper(direction);

prev = NULL;
cur = root;

for (i = 0; i < strlen(direction) && cur != NULL; i++)
{
prev = cur;
if (direction[i] == 'L')
cur = cur->llink;
else
cur = cur->rlink;
}
if (cur != NULL || i != strlen(direction))
{
printf("Insertion not possible\n");
freenode(temp);
return root;
}
if (direction[i-1] == 'L')
prev->llink = temp;
else
prev->rlink = temp;
return root;
}

void preorder(NODE root)
{
if (root != NULL)
{
printf("%d", root->info);
preorder(root->llink);
preorder(root->rlink);
}
}
void inorder(NODE root)
{
if (root != NULL)
{
inorder(root->llink);
printf("%d ", root->info);
inorder(root->rlink);
}
}

void postorder(NODE root)
{
if (root != NULL)
{
postorder(root->llink);
postorder(root->rlink);
printf("%d ", root->info);
}
}

void search(int item, NODE root, int *flag)
{
if (root != NULL)
{
search(item, root->llink, flag);
if (item == root->info)
{
*flag = 1;
return;
}
search(item, root->rlink, flag);
}
}

int choice, item, flag;
void main()
{
NODE root = NULL;
clrscr();
for (;;)
{
printf("1:Insert ");
printf("2:Preorder ");
printf("3:Inorder ");
printf("4:Postorder ");
printf("5:Search ");
printf("6:Exit ");
printf("Enter choice");
scanf("%d", &choice);
switch(choice)
{
case 1 :
printf("Enter item to be inserted \n");
scanf("%d", &item);
root = insert(item, root);
break;
case 2 :
if (root == NULL)
printf("Tree is empty\n");
else
{
printf("Preorder traversal\n");
preorder(root);
printf("\n");
}
break;
case 3:
if (root == NULL)
printf("Tree is empty\n");
else
{
printf("Inorder traversal is\n");
inorder(root);
printf("\n");
}
break;
case 4:
if (root == NULL)
printf("Tree is empty\n");
else
{
printf("Postorder traversal is\n");
postorder(root);
printf("\n");
}
break;
case 5:
if (root == NULL)
printf("Tree is empty\n");
else
{
printf("Enter item to search\n");
scanf("%d", &item);
flag = 0;
search(item, root, &flag);
if (flag == 1)
printf("Search successful\n");
else
printf("Unsuccesful search\n");
}
break;
default :
exit(0);
}
}
}

--------------------------------------------------------------------------------

4) /* Inorder,preorder and postorder traversal in a tree */
#include
#include
typedef struct list
{
int info;
struct list *l;
struct list *r;
}node;
node *ln;
main()
{
int ch,i,n;
node *root1;
clrscr();
ln=(node *)malloc(sizeof(node));
root1=(node *)malloc(sizeof(node));
root1=ln;
printf("How many node :");
scanf("%d",&n);
printf("\n1. Insert \n2. Delete \n3. Display \n4. Exit");
while(1)
{
printf("\nenter choice");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("enter the root element");
scanf("%d",&ln->info);
ln->l=ln->r=NULL;
for(i=1;i insert();
break;
case 2: ch=delete(root1);
printf("%d deleted",ch);
break;
case 3: printf("\n In order :");
inorder(root1);
printf("\n Pre order :");
preorder(root1);
printf("\n Post order :");
postorder(root1);
break;
case 4: exit(0);
}
}
}

insert()
{
node *p,*ptr,*pptr;
printf("enter the value:");
ptr=ln;
p=(node *)malloc(sizeof(node));
scanf("%d",&p->info);
p->l=p->r=NULL;
ptr=ln;
while(ptr!=NULL)
{
if(p->infoinfo)
{
pptr=ptr;
ptr=ptr->l;
if(ptr==NULL)
{
pptr->l=p;
break;
}
}
else
{
pptr=ptr;
ptr=ptr->r;
if(ptr==NULL)
{
pptr->r=p;
break;
}
}
}
}

preorder(node *ptr)
{
if(ptr!=NULL)
{
printf("%d : ",ptr->info);
preorder(ptr->l);
preorder(ptr->r);
}
}

inorder(node *ptr)
{
if(ptr!=NULL)
{
inorder(ptr->l);
printf("%d : ",ptr->info);
inorder(ptr->r);
}
}

postorder(node *ptr)
{
if(ptr!=NULL)
{
postorder(ptr->l);
postorder(ptr->r);
printf("%d : ",ptr->info);
}
}

--------------------------------------------------------------------------------

5) /* Postfix Expression evaluation */
#include
#include
#include
#include
#define MAX 25

int s[MAX],top=-1;

int isopnd(char a)/*check if the character is an operand*/
{
return(a>='0' && a<='9');
}

int isoprtr(char a)/*check if the character is an operator*/
{
return(a=='+' || a=='-' || a=='*' || a=='/');
}

int operate(char op,int temp2,int temp1)/*perform the given operation*/
{
int ans;
switch(op)
{
case '+':ans=temp1+temp2;break;
case '-':ans=temp1-temp2;
if(ans<0)
{
printf("subtraction resulting in negative quantity,program termination");
exit(0);
}
break;
case '*':ans=temp1*temp2;break;
case '/':ans=temp1/temp2;break;
}
return(ans);
}

void main()
{
char post[15],temp1,temp2,op;
int ans,i=-1;
clrscr();
printf("\nEnter the postfixed expression\n\n");
scanf("%s",post);
i=strlen(post);/*Start from reverse*/
while(--i>=0)
{
if (isopnd(post[i])) s[++top]=post[i]-'0';
else if(isoprtr(post[i]))
{
ans=operate(post[i],s[top--],s[top--]);
s[++top]=ans;
}
else
{
printf("unrecognizable character [%c] encountered",post[i]);
exit(1);
}
}
printf("\n\nthe value is %d",s[top]);
getch();
}

--------------------------------------------------------------------------------

6) /* Postfix evaluation with alphabets */
#include
#include
#include
#define MAX 25

int s[MAX],top=-1;
char dup[MAX];

int isopnd(char a)
{
return((a>='0' && a<='9')||(a>='a' && a<='z') ||(a>='A' && a<='Z'));
}

int isoprtr(char a)
{
return(a=='+' || a=='-' || a=='*' || a=='/');
}
int operate(char op,int temp1,int temp2)
{
int ans;
switch(op)
{
case '+':ans=temp1+temp2;break;
case '-':ans=temp1-temp2;
if(ans<0)
{ printf("subtraction resulting in negative quantity,program termination");
exit(0);
}
break;
case '*':ans=temp1*temp2;break;
case '/':ans=temp1/temp2;break;
}
return(ans);
}

void posteval()
{
char post[MAX],chrval[MAX][2],temp1,temp2,op;
int ans,i,j,k,l;
i=-1;j=k=l=0;
printf("\n\n");
do /*creates a copy of orignal string with substituted values*/
{ if(isoprtr(dup[j])) post[k++]=dup[j];
else if(isopnd(dup[j]))
{
if(dup[j]>='0' && dup[j]<='9') post[k++]=dup[j];
else
{
if(l==0)
{
chrval[l++][0]=dup[j];
printf("%c = ",dup[j]);
scanf(" %c",&chrval[l-1][1]);
post[k++]=chrval[l-1][1];
}
else
{
i=0;
while(i if (i==l)
{
chrval[l++][0]=dup[j];
printf("%c = ",dup[j]);
scanf(" %c",&chrval[l-1][1]);
post[k++]=chrval[l-1][1];
}
else post[k++]=chrval[i][1];
}
}
}
}while(dup[j++]!='\0');
post[k]='\0';
if(isoprtr(post[0]))
{
printf("unrecognizable postfix expression");
exit(1);
}
i=-1;
/*Evalution begins here*/
while(post[++i]!='\0')
{
if (isopnd(post[i])) s[++top]=post[i]-'0';
else if(isoprtr(post[i]))
{
ans=operate(post[i],s[top--],s[top--]);
s[++top]=ans;
}
else
{
printf("unrecognizable character [%c] encountered",post[i]);
exit(1);
}
}
printf("\n\nthe value is %d",s[top]);
}

void head()
{
clrscr();
printf("**************************************************************************\n\n");
printf("\tEVALUATING A POSTFIXED EXPRESSION WITH ALPHABETS\n\n");
printf("**************************************************************************\n\n");
}

void main()
{
char ans;
head();
printf("\n\n");
nu:
printf("\nEnter the postfixed expression\n\n");
scanf("%s",dup);
repeat:
posteval();
printf("\n\n press\n\tn--to evaluate a new expression\n\t");
printf("r--to repeat the same expression with new values\n\t");
printf("q--to quit ");
a:
ans=getch();
putch(ans);
switch(ans)
{
case 'n':head();goto nu;
case 'r':head();
printf("\nPostfix expression is %s",dup);
goto repeat;
case 'q':break;
default:
printf("invalid entry(press n/r/q only)");
goto a;
}
}

--------------------------------------------------------------------------------

Infix to postfix:

Algorithm
1) Examine the next element in the input.
2) If it is an operand, output it.
3) If it is opening parenthesis, push it on stack.
4) If it is an operator, then
i) If stack is empty, push operator on stack.
ii) If the top of the stack is opening parenthesis, push operator on stack.
iii) If it has higher priority than the top of stack, push operator on stack.
iv) Else pop the operator from the stack and output it, repeat step 4.
5) If it is a closing parenthesis, pop operators from the stack and output them until an opening parenthesis is encountered. pop and discard the opening parenthesis.
6) If there is more input go to step 1
7) If there is no more input, unstack the remaining operators to output.

Example:

Suppose we want to convert 2*3/(2-1)+5*(4-1) into Postfix form

Char Scanned Stack Contents(Top on right) Postfix Expression
2 Empty 2
* * 2
3 * 23
/ / 23*
( /( 23*
2 /( 23*2
- /(- 23*2
1 /(- 23*21
) / 23*21-
+ + 23*21-/
5 + 23*21-/5
* +* 23*21-/5
( +*( 23*21-/5
4 +*( 23*21-/54
- +*(- 23*21-/54
1 +*(- 23*21-/541
) +* 23*21-/541-
Empty 23*21-/541-*+
So, the Postfix Expression is 23*21-/541-*+

7) /* Infix to postfix */
#include
#include
#include
#define MAX 25
int s[MAX],top=-1;
void intopost();

int pre(char a)
{
int b;
switch(a)
{
case '(':b=0;break;
case '+':
case '-':b=1;break;
case '*':
case '/':b=2;break;
case '^':b=3;break;
}
return(b);
}

int isalnum(char a)
{
return((a>='a' && a<='z')||(a>='A' && a<='Z') || (a>='0' && a<='9'));
}

int isopr(char a)
{
int b=0;
switch(a)
{
case '+':
case '-':
case '*':
case '/':
case '^':b=1;break;
}
return(b);
}

void intopost()
{
char in[MAX],post[MAX],a;
int ti,tp;
unsigned long ab=0;
ti=tp=-1;
clrscr();
s[++top]='(';
printf("\n\n\nEnter the infix expression\n\n");
scanf("%s",in);
while(in[++ti]!='\0')
{
if(isalnum(in[ti])) post[++tp]=in[ti];
else if(isopr(in[ti]))
{
while(pre(in[ti])<=pre(s[top]))
post[++tp]=s[top--];
s[++top]=in[ti];
}
else if(in[ti]=='(') s[++top]='(';
else if(in[ti]==')')
{
while(s[top]!='(')
{
post[++tp]=s[top--];
}
top--;
}
else
{
printf("invalid symbol [%c] encountered ,abnormal program termination",in[ti]);
getch();
exit(1);
}
}
while(s[top]!='(') post[++tp]=s[top--];
post[++tp]='\0';
printf("\n\nthe postfixed expression is %s",post);
}

void main()
{
char a;
do{
intopost();
printf("\n\nDo you want to continue?(y/*) ");
a=getch();
}
while((a=='y') ||(a=='Y'));
}

--------------------------------------------------------------------------------

Infix to prefix:

Algorithm

1) Reverse the input string.
2) Examine the next element in the input.
3) If it is operand, add it to output string.
4) If it is Closing parenthesis, push it on stack.
5) If it is an operator, then
i) If stack is empty, push operator on stack.
ii) If the top of stack is closing parenthesis, push operator on stack.
iii) If it has same or higher priority than the top of stack, push operator on stack.
iv) Else pop the operator from the stack and add it to output string, repeat step 5.
6) If it is a opening parenthesis, pop operators from stack and add them to output string until a closing parenthesis is encountered. Pop and discard the closing parenthesis.
7) If there is more input go to step 2
8) If there is no more input, unstack the remaining operators and add them to output string.
9) Reverse the output string.

Example:

Suppose we want to convert 2*3/(2-1)+5*(4-1) into Prefix form: Reversed Expression: )1-4(*5+)1-2(/3*2
Char Scanned Stack Contents(Top on right) Prefix Expression(right to left)
) )
1 ) 1
- )- 1
4 )- 14
( Empty 14-
* * 14-
5 * 14-5
+ + 14-5*
) +) 14-5*
1 +) 14-5*1
- +)- 14-5*1
2 +)- 14-5*12
( + 14-5*12-
/ +/ 14-5*12-
3 +/ 14-5*12-3
* +/* 14-5*12-3
2 +/* 14-5*12-32
Empty 14-5*12-32*/+

8) /* Infix to prefix */
#include
#include
#include

int s[25],top=-1;

void push(char x)
{
s[++top]=x;
}

int pop()
{
return(s[top--]);
}

void abn()
{
printf("\nInvalid expression encountered abnormal termination");
exit(1);
}

int isalnum(char a)
{

return((a>='a' && a<='z') || (a>='A' && a<='Z') || (a>='0' && a<='9'));
}

int isopr(char a)
{
return(a=='+' || a=='-' || a=='*' || a=='/' || a=='^');
}
int pre(char a)
{
int i=0;
switch(a)
{
case '+':case '-':i=1;break;
case '*':case '/':i=2;break;
case '^':i=3;break;
}
return(i);
}

void intopre()
{
char in[15],p[15],rank=0;
int i,j,k;
i=0;j=14;
fflush(stdin);
clrscr();
printf("\n\nEnter the infix expression\n ");
scanf("%s",in);
while(in[i]!='\0') i++;

while((--i)>=0)
{
if(isalnum(in[i])){p[j--]=in[i];rank++;}
else if(isopr(in[i]))
{
while(pre(in[i])<=pre(s[top])) p[j--]=pop();
push(in[i]);
rank--;
}
else if(in[i]==')') push(')');
else if(in[i]=='(')
{
while(s[top]!=')')
{
if(top==0)
{
abn();
}
p[j--]=pop();
}
pop(s[top]);
}
}
if(rank!=1) abn();
while(top>0) p[j--]=pop();
printf("\nthe prefix expression is\n\n ");
for(k=j+1;k<=14;k++)
printf("%c",p[k]);
}

void main()
{
char ans;
push('#');
do{
intopre();
printf("\n\npress y to continue? ");
ans=getch();
putch(ans);
}while(ans=='y'|| ans=='Y');
}

--------------------------------------------------------------------------------

9) /* Infix to prefix and postfix */
#include
#include
#include
#define MAX 25

int s[MAX],top=-1;
/*function returns precedence*/
int pre(char a)
{
int b=0;
switch(a)
{
case '(':b=0;break;
case '+':case '-':b=1;break;
case '*':case '/':b=2;break;
case '^':b=3;break;
}
return(b);
}

int isalnum(char a)
{
return((a>='a' && a<='z')||(a>='A' && a<='Z') || (a>='0' && a<='9'));
}

int isopr(char a)
{
int b=0;
switch(a)
{
case '+':
case '-':
case '*':
case '/':
case '^':b=1;break;
}
return(b);
}
void head()
{
printf("***************************************************************************\n\n");
printf("\t\t INFIX TO POSTFIX AND PREFIX\n\n");
printf("***************************************************************************\n\n");
}
void abn(int a)
{
printf("\nInvalid expression encountered");
if(a==2) printf(" while converting to prefix");
printf("\nabnormal program termination");
exit(1);

}

void intop()
{
char in[MAX],p[MAX],post[MAX],a;
int ti,tp,rank,i,j,k;
rank=0;
i=0;j=14;
ti=tp=-1;
clrscr();
head();
s[++top]='(';
printf("\n\n\nEnter the infix expression\n\n");
scanf("%s",in);
/*postfixing*/
while(in[++ti]!='\0')
{
if(isalnum(in[ti])){post[++tp]=in[ti];rank++;}
else if(isopr(in[ti]))
{
while(pre(in[ti])<=pre(s[top]))
post[++tp]=s[top--];
s[++top]=in[ti];
rank--;
}
else if(in[ti]=='(') s[++top]='(';
else if(in[ti]==')')
{
while(s[top]!='(')
{
post[++tp]=s[top--];
}
top--;
}
else
{
printf("invalid symbol [%c] encountered ,abnormal program termination",in[ti]);
getch();
exit(1);
}
}
if(rank!=1) abn(1);
while(s[top]!='(') post[++tp]=s[top--];
post[++tp]='\0';
printf("\n\nthe postfixed expression is \n\n %s\n",post);
/*prefixing*/
rank=0;
while(in[i]!='\0') i++;
while((--i)>=0)
{
if(isalnum(in[i])){p[j--]=in[i];rank++;}
else if(isopr(in[i]))
{
while(pre(in[i])<=pre(s[top])) p[j--]=s[top--];
s[++top]=in[i];
rank--;
}
else if(in[i]==')') s[++top]=')';
else if(in[i]=='(')
{
while(s[top]!=')')
{
if(top==0)
{
abn(2);
}
p[j--]=s[top--];
}
top--;
}
}
if(rank!=1) abn(2);
while(s[top]!='(') p[j--]=s[top--];
printf("\nthe prefix expression is\n\n ");
for(k=j+1;k<=14;k++)
printf("%c",p[k]);
}

void main()
{
char ans;
do{
intop();
printf("\n\npress y to continue? ");
ans=getch();
putch(ans);
}while(ans=='y'|| ans=='Y');
}

--------------------------------------------------------------------------------

10) /* Postfix to Prefix */
/*Convert Postfix to Prefix */
#define MAX 100

void pop (char *a1);
void push(char *str);

char stack[MAX][MAX];
int top =-1;
main()
{

char s[MAX], str1[MAX], str2[MAX], str[MAX];
char s1[2], temp[2];

int i = 0;

clrscr();
printf("Enter the postfix expression; ");
gets (s);

while(s[i]!=`\0')
{
/*skip whitespace, if any */
if (s[i] == '')
i++;

if(s[i] == `%' || s[i] == `*' || s[i] == `_' || s[i]== `+' || s[i] == `/')
{

pop (str1);
pop (str2);

temp[0] = s[i];
temp[1] = `\0';

strcpy (str, temp);
strcat(str, str2);
strcat(str, str1);

push(str);
}
else
{

temp[0] = s[i];
temp[1] = `\0';
strcpy (s1, temp);

push (s1);
}
i++;
}
printf("\n%s",stack[0]);
}

void pop(char*a1)
{
if(top == -1)
{
printf("\nStack is empty");
exit(1);
}
else
{
strcpy (a1, stack[top]);
top--;
}
}

void push (char *str)
{
if(top == MAX - 1)
printf("\nstack is full");
else
{
top++;
strcpy(stack[top], str);
}
}

--------------------------------------------------------------------------------

11) /* Postfix to Infix */

#define Max 100
void pop (char*);
void push(char*);
char stack[MAX] [MAX];
int top = -1

main()
{

char s[MAX], str1[MAX], str2[MAX], str[MAX];
char s1[2],temp[2];
inti=0;

clrscr( ) ;
printf("\Enter the postfix expression; ")
get(s);
while (s[i]!`\0')
{

/*skip whitespace, if any*/

if(s[i] == ' ' )
i++;

if (s[i] == `%' || s[i] == `*'|| s[i] == `-' || s[i] == `+' || s[i] == `/')
{

pop(str1);
pop(str2);

temp[0] =`(';
temp[1] =`\0';

strcpy(str, temp);
strcat(str, str2);

temp[0] = s[i];
temp[1] = `\0'
strcat(str,temp);
strcat(str, str1);

temp[0] =`)';
temp[1] =`\0';
strcat(str,temp);

push(str);

}
else
{

temp[0]=s[i];
temp[1]=`\0';
strcpy(s1, temp);
push(s1);
}
i++;
}
printf("\n%s", stack[0]);
}

void pop(char *a1)
{

strcpy(a1,stack[top]);
top--;
}

void push (char*str)
{
if(top == MAX - 1)
printf("\nstack is full");
else
{
top++;
strcpy(stack[top], str);
}
}

Responses

No responses found. Be the first to respond and make money from revenue sharing program.

Feedbacks

Popular Tags

What are tags ?

Search Tags

(No tags found.)

Post Feedback

This is a strictly moderated forum. Only approved messages will appear in the site. Please use 'Spell Check' in Google toolbar before you submit.
You must Sign In to post a response.

	Next Resource: QUEUE & STACK
	Previous Resource: Overview of Files Concept.
	Return to Discussion Resource Index
	Post New Resource
	Category: Computer & Technology

Post resources and earn money!

Related Resources

Fresher Jobs

Resources

Colleges

TREE

Responses

Post Feedback