Data Structures Programs on STACK

/* Decimal to binary conversion uses stack */

#include <stdio.h>

#include <conio.h>

void main ( )

{

int stack[30], dec, rem, top=0;

clrscr();

printf ("\nEnter decimal number:\n");

scanf("%d", &dec);

while (dec!=0)

{

rem=dec%2;

top++;

stack[top]=rem;

dec=dec/2;

}

printf ("\nThe equivalent binary number is\n");

for (; top>0; top--)

{

printf ("%d", stack[top]);

}

getch ( );

}

/* Towers of Hanoi problem using recursion */

#include<stdio.h>

#include<conio.h>

void main()

{

int n;

char A='A',B='B',C='C';

void hanoi(int, char, char, char);

clrscr();

printf ("Enter Number of Disks:");

scanf("%d",&n);

printf("\n\n Tower of Hanoi problem with %d disks\n",n);

printf("Sequence is :\n");

hanoi (n, A, B, C);

printf ("\n");

getch();

}

void hanoi(int n, char A, char B, char C)

{

if (n!=0)

{

hanoi (n-1,A,C,B);

printf ("Move disk %d from %c to %c\n",n,A,C);

hanoi (n-1,B,A,C);

}

}

/* Convert Infix Expression into Postfix Expression */

#include<stdio.h>

#include<conio.h>

#include<string.h>

char stack [30];

int top = -1;

void infix_to_postfix (char *);

void push(char);

char pop ( );

void main ( )

{

char infix [30];

clrscr();

printf ("\n Enter the infix expression:\n");

gets (infix);

infix_to_postfix (infix);

getch ( );

}

void push (char sym)

{

if (top >= 29)

{

printf ("\n stack is overflow");

getch ( );

return;

}

else

{

top = top + 1;

stack [top] = sym;

}

}

char pop ( )

{

char i;

if (top ==-1)

{

printf ("\n stack is empty");

return(0);

}

else

{

i = stack [top];

top = top - 1;

}

return (i);

}

int prec (char ch)

{

if (ch=='^')

{

return (5);

}

else if (ch=='*' || ch=='/')

{

return (4);

}

else if (ch=='+' || ch=='-')

{

return (3);

}

else

{

return (2);

}

}

void infix_to_postfix (char infix [ ])

{

int length;

static int index = 0, pos= 0;

char symbol, temp;

char postfix [50];

length = strlen(infix);

while (index < length)

{

symbol = infix[index];

switch (symbol)

{

case '(' : push (symbol);

break;

case ')' : temp = pop ( );

while (temp != '(')

{

postfix [pos]=temp;

pos++;

temp=pop ();

}

break;

case '+' :

case '-' :

case '*' :

case '/' :

while (prec (stack[top]) >= prec (symbol))

{

temp = pop();

postfix [pos]= temp;

pos++;

}

push (symbol);

break;

default:postfix [pos++] = symbol;

break;

}

index++;

}

while (top>=0)

{

temp = pop ( );

postfix [pos++] = temp;

}

postfix [pos++] = '\0';

printf("\nEquivalent postfix expression is:\n");

puts (postfix);

return;

}

/* Program to Evaluate Postfix Notation */

#include<stdio.h>

#include<conio.h>

#include<string.h>

void main( )

{

char S[80];

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

clrscr ( );

printf ("\n Enter the valid postfix notation :");

gets(S);

n = strlen(S);

printf ("The value of the postfix notation is :");

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+1;

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

x = S[i] - 48;

stack[top] = x;

x=0;

}

}

printf("%d", stack[top]);

getch( );

}