PROGRAM TO BUILD EXPRESSION TREE USING STACK

 /*

Algorithm

  1 Take any postfix epression 
  2 Run the loop If it is an operand then simply push it to stack 
  3 Else if it is the operator then pop two operand  from the stack 
  4 Make the first and  second poped operand as a left child  and right child of current operand respectively then push it to stack 
  5 Continue the steps and run the loop till the length of postfix expression Anonymous Anonymous

*/

• #include<stdio.h>

• #include<stdlib.h>

• #include<string.h>

• #define SIZE 50

• struct express_tree

• {

• char ch;

• struct express_tree *left,*right;

• };

• struct stack

• {

• struct express_tree **array;

• int top;

• };

• /*...................................................................*/

• struct stack* create_stack()

• {

• struct stack *st=(struct stack *)malloc(sizeof(struct stack));

• st->array=malloc(sizeof(struct express_tree)*SIZE);

• return st;

• }

• /*...................................................................*/

• int is_empty_stack(struct stack *s)

• {

• return(s->top==-1);

• }

• /*...................................................................*/

• int is_full_stack(struct stack *s)

• {

• return(s->top==SIZE-1);

• }

• /*...................................................................*/

• void push(struct stack *s,struct express_tree *new)

• {

• if(is_full_stack(s))

• return;

• s->array[++s->top]=new;

• }

• /*...................................................................*/

• struct express_tree* pop(struct stack *s)

• {

• if(is_empty_stack(s))

• return NULL;

• return s->array[s->top--];

• }

• /*......................................................................*/

• void delete_stack(struct stack *s)

• {

• if(s)

• {

• if(s->array)

• free(s->array);

• free(s);

• }

• }

• /*......................................................................*/

• void delete_express_tree(struct express_tree *expression)

• {

• if(expression)

• {

• delete_express_tree(expression->left);

• delete_express_tree(expression->right);

• free(expression);

• }

• }

• /*......................................................................*/

• void display_tree(struct express_tree *root)

• {

• if(root)

• {

• display_tree(root->left);

• display_tree(root->right);

• printf("%c\n",root->ch);

• }

• }

• /*......................................................................*/

• struct stack* tree_making(char str[])

• {

• struct stack *s=create_stack();

• struct express_tree *new_node,*t2,*t1,*new;

• int i;

• for(i=0;i<strlen(str);i++)

• {

• if(isalpha(str[i]))

• {

• new_node=malloc(sizeof(struct express_tree));

• new_node->ch=str[i];

• new_node->left=new_node->right=NULL;

• push(s,new_node);

• }

• else

• {

• t2=pop(s);

• t1=pop(s);

• new=malloc(sizeof(struct express_tree));

• new->ch=str[i];

• new->left=t1;

• new->right=t2;

• push(s,new);

• }

• }

• return s;

• }

• /*......................................................................*/

• int main()

• {

• struct express_tree *temp;

• struct stack *s;

• char str[SIZE];

• printf("\nenter any postfix expression ");

• fgets(str,SIZE,stdin);

• s=tree_making(str);

• temp=pop(s);

• printf("expression tree\n");

• display_tree(temp);

• delete_express_tree(temp);

• delete_stack(s);

• return 0;

• }

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

Simple stacks implementation using linked list : PUSH , POP

/*simple stacks implementation using linked list */

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

struct stack
 {
int data;
  struct node *link;
 };
void push(struct stack **top,int val)
 {
  struct stack *temp;
  temp =(struct stack *)malloc(sizeof(struct stack));
  if(temp==NULL)
  printf("\nstack overflow\n");
temp->data=val;
temp->link=*top;
*top=temp;
 }
int pop(struct stack **top)
 {
  struct stack *temp;
  int ret;
  if(*top==NULL)
  {
  printf("\nstack underflow\n");
  return NULL;
  }
  temp=*top;
  ret=temp->data;
  (*top)=(*top)->link;
  free(temp);
  return ret;
 }

void main()
 {
  struct stack *s1=NULL;
  int i;
 
  push(&s1,12);
  push(&s1,20);
  push(&s1,1);
  push(&s1,13);
 
  i=pop(&s1);          // i=13
  i=pop(&s1);          // i=1
 
  printf("%d\n",i);   // prints 1
 }

Simple Stacks Implementation using arrays : PUSH , POP

/*Simple Stacks Implementation : PUSH , POP*/

#include<stdio.h>

#define max 10

struct stack
 {
  int arr[max];
  int top;
 };
void ini(struct stack *s)
 {
  s->top=(-1);
 }
void push(struct stack *s,int val)
 {
  if(s->top==(max-1))
  {
  printf("\nSTACK OVERFLOW\n");
  return;
 }

  s->top++;
  s->arr[s->top]=val;

 }
int pop(struct stack *s)
 {
  int data;
  if(s->top==-1)
    {
  printf("\nSTACK UNDERFLOW\n");
return;
}


data=s->arr[s->top];
s->top--;
return data;

}
void main()
 {
  struct stack s1;
  int i;
  ini(&s1);
  push(&s1,10);
  push(&s1,40);
  push(&s1,20);
  i=pop(&s1);
  printf("\n%d\n",i);
  i=pop(&s1);
  printf("\n%d\n",i);
  i=pop(&s1);
  printf("\n%d\n",i);
 }