DATA STRUCTURE:ASSIGNMENT NO.6:STACK
PRACTICE PROGRAM:-
4) Write a C Program to sort a stack using temporary stack.
ANS:
#include <stdio.h>
#include <conio.h>
#define max 100
typedef struct stack
{
int top;
int item[max];
} STACK;
int isEmpty(STACK *ps)
{
if (ps->top == -1)
return 1;
else
return 0;
}
int isFull(STACK *ps)
{
if (ps->top == max - 1)
return 1;
else
return 0;
}
void push(STACK *ps, int n)
{
if (isFull(ps))
printf("\n Stack is full----");
else
{
ps->top++;
ps->item[ps->top] = n;
}
}
int pop(STACK *ps)
{
int x;
if (isEmpty(ps))
printf("\n Stack is Empty---");
else
{
x = ps->item[ps->top];
ps->top--;
}
return x;
}
void display(STACK *ps)
{
int i;
for (i = 0; i < ps->top; i++)
{
printf("\t%d", ps->item[i]);
}
}
void insertion_sort(STACK *ps)
{
int i, j, temp;
for (i = 0; i < ps->top; i++)
{
temp = ps->item[i];
for (j = i - 1; j >= 0 && ps->item[j] > temp; j--)
{
ps->item[j + 1] = ps->item[j];
}
ps->item[j + 1] = temp;
}
}
int main()
{
STACK s1, temp;
int choice, n;
s1.top = -1;
do
{
printf("\n------------");
printf("\n1.push\n2.Exit");
printf("\n------------");
printf("\n Enter your choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("\n Enter push element:");
scanf("%d", &n);
push(&s1, n);
break;
}
} while (choice != 2);
printf("\n The original stack is:\n");
display(&s1);
insertion_sort(&s1);
printf("\n The Sorted stack is:\n");
display(&s1);
}
--------------------------------------------------------------------------------
SET A:
1) Write a C program to implement Static implementation of stack of integers with following
operation:
-Initialize(), push(), pop(), isempty(), isfull(), display().
ANS:
#include <stdio.h>
#include <conio.h>
#define max 30
typedef struct stack
{
int a[max];
int top;
} STACK;
void initStack(STACK *ps)
{
ps->top = -1;
}
void push(STACK *ps, int n)
{
if (!isEmpty(&ps))
{
ps->top++;
ps->a[ps->top] = n;
}
else
{
printf("\n Stack is empty!");
return;
}
}
int pop(STACK *ps)
{
int n;
if (!isFull(&ps))
{
n = ps->a[ps->top];
ps->top--;
return n;
}
else
{
printf("\n Stack is full!");
return 0;
}
}
int isEmpty(STACK *ps)
{
if (ps->top == -1)
{
return 1;
}
else
{
return 0;
}
}
int isFull(STACK *ps)
{
if (ps->top == max - 1)
{
return 1;
}
else
{
return 0;
}
}
void display(STACK *ps)
{
int i;
for (i = 0; i <= ps->top; i++)
{
printf("\t%d", ps->a[i]);
}
}
int main()
{
int n, choice;
STACK s1;
initStack(&s1);
do
{
printf("\n----------------------------");
printf("\n1.push \n2.pop \n 3.display \n4.Exit");
printf("\n----------------------------");
printf("\n Enter your choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
if (!isFull(&s1))
{
printf("\n Enter push element:");
scanf("%d", &n);
push(&s1, n);
}
break;
case 2:
if (!isEmpty(&s1))
{
n = pop(&s1);
printf("\n The pop element is:%d", n);
}
else
{
printf("\n Stack is empty!");
}
break;
case 3:
if (!isEmpty(&s1))
{
printf("\n The Stack is:\n");
display(&s1);
}
else
{
printf("\n Stack is Empty!");
}
break;
}
} while (choice != 4);
}
------------------------------------------------------------------------------------
2) Write a C program to implement Dynamic implementation of stack of integers with
following operation:
-Initialize(), push(), pop(), isempty(), display().
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *next;
} STACK;
int isEmpty(STACK *ps)
{
return ps == NULL ? 1 : 0;
}
STACK *push(STACK *ps, int n)
{
STACK *new_node;
new_node = (STACK *)malloc(sizeof(STACK));
new_node->next = NULL;
new_node->data = n;
new_node->next = ps;
ps = new_node;
return ps;
}
STACK *pop(STACK *ps)
{
int x;
STACK *temp = ps;
if (!isEmpty(ps))
{
x = temp->data;
ps = temp->next;
free(temp);
printf("\n The pop element is:%d", x);
return ps;
}
else
{
printf("\n Stack is Empty!");
return ps;
}
}
void display(STACK *list)
{
while (list != NULL)
{
printf("\t%d", list->data);
list = list->next;
}
}
int main()
{
int n, choice;
STACK *s1 = NULL;
do
{
printf("\n---------------");
printf("\n1.push\n2.pop\n3.display\n4.Exit");
printf("\n------------------");
printf("\n Enter your choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("\n Enter push element:");
scanf("%d", &n);
s1 = push(s1, n);
break;
case 2:
if (!isEmpty(s1))
{
s1 = pop(s1);
}
else
{
printf("\n Stack is empty!");
}
break;
case 3:
if (!isEmpty(s1))
{
printf("\n The stack is:\n");
display(s1);
}
else
{
printf("\n The stack is Empty!");
}
break;
}
} while (choice != 4);
getch();
return 0;
}
----------------------------------------------------------------------------------------
3) Write a C program to reverse each word of the string by using static and dynamic
implementation of stack.
Example: Input - This is an input string
Output – sihT si na tupni gnirts.
ANS:
//dynamic implemantation...
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#define max 100
typedef struct stack
{
char data;
struct stack *next;
} STACK;
int isEmpty(STACK *s)
{
return (s == NULL) ? 1 : 0;
}
STACK *push(STACK *s, char n)
{
STACK *new_node, *temp;
new_node = (STACK *)malloc(sizeof(STACK));
new_node->next = NULL;
new_node->data = n;
new_node->next = s;
s = new_node;
return s;
}
STACK *pop(STACK *s)
{
char n;
STACK *temp = s;
n = temp->data;
s = temp->next;
free(temp);
printf("%c", n);
return s;
}
int main()
{
STACK *s = NULL, *temp;
char input[max], ch;
int i;
printf("\nEnter Sentence:\n");
gets(input);
for (i = 0; i < strlen(input); i++)
{
if (input[i] != ' ')
{
s = push(s, input[i]);
}
else
{
while (!isEmpty(s))
{
s = pop(s);
}
printf(" ");
}
}
while (!isEmpty(s))
{
s = pop(s);
}
getch();
return 0;
}
//static implementaion...
#include <stdio.h>
#include <conio.h>
#include <string.h>
#define max 100
typedef struct stack
{
int top;
char item[max];
} STACK;
void initStack(STACK *ps)
{
ps->top = -1;
}
int isEmpty(STACK *ps)
{
if (ps->top == -1)
{
return 1;
}
else
{
return 0;
}
}
int isFull(STACK *ps)
{
if (ps->top == max - 1)
{
return 1;
}
else
{
return 0;
}
}
void push(STACK *ps, char n)
{
if (!isFull(ps))
{
ps->top++;
ps->item[ps->top] = n;
}
else
{
printf("\n Stack is full...!");
}
}
char pop(STACK *ps)
{
char x;
if (!isEmpty(ps))
{
x = ps->item[ps->top];
ps->top--;
}
else
{
printf("\n Stack is empty!");
}
return x;
}
int main()
{
int len = 0, i;
STACK s1;
char input[max];
initStack(&s1);
printf("\n Enter sentence:");
gets(input);
for (i = 0; i < strlen(input); i++)
{
if (input[i] != ' ')
{
push(&s1, input[i]);
}
else
{
while (!isEmpty(&s1))
{
printf("%c", pop(&s1));
}
printf(" ");
}
}
while (!isEmpty(&s1))
{
printf("%c", pop(&s1));
}
getch();
return 0;
}
----------------------------------------------------------------------
SET B :
1) Write a ‘C’ program which accepts the string and check whether the string is Palindrome or
not using stack. (Use Static/Dynamic implementation of Stack).
ANS:
//static implementation...
#include <stdio.h>
#include <conio.h>
#include <string.h>
#define max 50
typedef struct stack
{
int top;
char a[max];
} STACK;
void initStack(STACK *ps)
{
ps->top = -1;
}
int isEmpty(STACK *ps)
{
return (ps->top == -1) ? 1 : 0;
}
int isFull(STACK *ps)
{
return (ps->top == max - 1) ? 1 : 0;
}
void push(STACK *ps, char ch)
{
if (isFull(ps))
printf("\n Stack is full...!");
else
{
ps->top++;
ps->a[ps->top] = ch;
}
}
char pop(STACK *ps)
{
char x;
if (isEmpty(ps))
printf("\n Stack is Empty!");
else
{
x = ps->a[ps->top];
ps->top--;
}
return x;
}
int main()
{
STACK s1;
initStack(&s1);
char input[max], output[max], ch, temp[max];
int len, i;
printf("\n Enter a string to check it palindrome or not:");
gets(input);
strcpy(temp, input);
len = strlen(temp);
for (i = 0; i < len; i++)
{
push(&s1, temp[i]);
}
for (i = 0; i < len; i++)
{
output[i] = pop(&s1);
}
output[i] = '\0';
if (strcmp(output, input) == 0)
{
printf("\n String is palindrome!");
}
else
{
printf("\n The String not a palindrome!");
}
getch();
return 0;
}
----------------------------------------------------------------------------------------
2) Write a ‘C’ program to read a postfix expression, evaluate it and display the result. (Use
Static/Dynamic implementation of Stack).
ANS:
//static implementation...
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <ctype.h>
#define max 50
typedef struct stack
{
int top;
int item[max];
} STACK;
void initStack(STACK *ps)
{
ps->top = -1;
}
int isEmpty(STACK *ps)
{
return (ps->top == -1) ? 1 : 0;
}
int isFull(STACK *ps)
{
return (ps->top == max - 1) ? 1 : 0;
}
void push(STACK *ps, int n)
{
if (isFull(ps))
printf("\n Stack is full!");
else
{
ps->top++;
ps->item[ps->top] = n;
}
}
int pop(STACK *ps)
{
int x;
if (isEmpty(ps))
printf("\n Stack is Empty!");
else
{
x = ps->item[ps->top];
ps->top--;
}
return x;
}
int main()
{
int a, i, len, op1, op2, result = 0;
char postfix[max];
STACK s1;
initStack(&s1);
printf("\n Enter postfix string :");
gets(postfix);
len = strlen(postfix);
for (i = 0; i < len; i++)
{
if (isalnum(postfix[i]))
{
if (postfix[i] >= '0' && postfix[i] <= '9')//also used isdigit();
{
push(&s1, (postfix[i] - '0'));
}
else
{
printf("\n Enter value for %c:", postfix[i]);
scanf("%d", &a);
push(&s1, a);
}
}
else
{
switch (postfix[i])
{
case '+':
op2 = pop(&s1);
op1 = pop(&s1);
result = op1 + op2;
push(&s1, result);
break;
case '-':
op2 = pop(&s1);
op1 = pop(&s1);
result = op1 - op2;
push(&s1, result);
break;
case '*':
op2 = pop(&s1);
op1 = pop(&s1);
result = op1 * op2;
push(&s1, result);
break;
case '/':
op2 = pop(&s1);
op1 = pop(&s1);
result = op1 / op2;
push(&s1, result);
break;
case '%':
op2 = pop(&s1);
op1 = pop(&s1);
result = op1 % op2;
push(&s1, result);
break;
}
}
}
result = pop(&s1);
printf("\n The result is:%d", result);
getch();
return 0;
}
//dynamic implementation...
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
typedef struct stack
{
int data;
struct stack *next;
} STACK;
int isEmpty(STACK *ps)
{
return (ps == NULL) ? 1 : 0;
}
STACK *push(STACK *ps, int n)
{
STACK *new_node, *temp;
new_node = (STACK *)malloc(sizeof(STACK));
new_node->next = NULL;
new_node->data = n;
if (isEmpty(ps))
{
ps = temp = new_node;
}
else
{
new_node->next = ps;
ps = new_node;
}
return ps;
}
STACK *operate(STACK *s, int op1, int op2, char operator)
{
int result = 0;
switch (operator)
{
case '+':
result = op1 + op2;
s = push(s, result);
break;
case '-':
result = op1 - op2;
s = push(s, result);
break;
case '*':
result = op1 * op2;
s = push(s, result);
break;
case '/':
result = op1 / op2;
s = push(s, result);
break;
case '%':
result = op1 % op2;
s = push(s, result);
break;
}
return s;
}
STACK *popToTime(STACK *ps, char op)
{
int op1 = 0, op2 = 0, i = 1, n;
STACK *temp;
if (isEmpty(ps))
printf("\n Stack is Empty!");
else
{
while (i <= 2)
{
if (i == 1)
{
temp = ps;
op2 = temp->data;
ps = temp->next;
free(temp);
}
else
{
temp = ps;
op1 = temp->data;
ps = temp->next;
free(temp);
}
i++;
}
ps = operate(ps, op1, op2, op);
}
return ps;
}
STACK *pop(STACK *ps)
{
int result = 0;
STACK *temp = ps;
result = temp->data;
ps = temp->next;
free(temp);
printf("\n The result is:%d", result);
return ps;
}
void main()
{
int a, i, len;
char postfix[50];
STACK *s1 = NULL;
printf("\n Enter postfix string :");
gets(postfix);
len = strlen(postfix);
for (i = 0; i < len; i++)
{
if (isalnum(postfix[i]))
{
if (postfix[i] >= '0' && postfix[i] <= '9')
{
s1 = push(s1, (postfix[i] - '0'));
}
else
{
printf("\n Enter value for %c:", postfix[i]);
scanf("%d", &a);
s1 = push(s1, a);
}
}
else
{
s1 = popToTime(s1, postfix[i]);
}
}
s1 = pop(s1);
getch();
}
----------------------------------------------------------------------------------------
3) Write a ‘C’ program to accept an infix expression, convert it into its equivalent postfix
expression and display the result. (Use Static/Dynamic implementation of Stack).
ANS:
//static implementation...
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <ctype.h>
#define max 50
typedef struct stack
{
int top;
char item[max];
} STACK;
void initStack(STACK *ps)
{
ps->top = -1;
}
int isEmpty(STACK *ps)
{
return (ps->top == -1) ? 1 : 0;
}
int isFull(STACK *ps)
{
return (ps->top == max - 1) ? 1 : 0;
}
void push(STACK *ps, char ch)
{
if (isFull(ps))
printf("\n Stack is full...");
else
{
ps->top++;
ps->item[ps->top] = ch;
}
}
char pop(STACK *ps)
{
char x;
if (isEmpty(ps))
printf("\n Stack is Empty...");
else
{
x = ps->item[ps->top];
ps->top--;
}
return x;
}
int main()
{
STACK s1;
char infix[20], postfix[20], ch;
int i, j = 0, len;
initStack(&s1);
printf("\n Enter infix string:");
gets(infix);
len = strlen(infix);
for (i = 0; i < len; i++)
{
if (isalnum(infix[i]))
{
postfix[j] = infix[i];
j++;
}
switch (infix[i])
{
case '+':
case '-':
case '*':
case '/':
case '%':
case '(':
push(&s1, infix[i]);
break;
case ')':
while ((ch = pop(&s1)) != '(')
{
postfix[j] = ch;
j++;
}
break;
}
}
while (!isEmpty(&s1))
{
postfix[j] = pop(&s1);
j++;
}
postfix[j] = '\0';
printf("\n The postfix string is:%s", postfix);
getch();
return 0;
}
---------------------------------------------------------------------------------
SET C:
1) Write a program to check whether the contents of two stacks are identical.
ANS:
#include <stdio.h>
#include <conio.h>
#define max 100
typedef struct stack
{
int item[max];
int top;
} STACK;
void initStack(STACK *s)
{
s->top = -1;
}
int isEmpty(STACK *s)
{
return (s->top == -1) ? 1 : 0;
}
int isFull(STACK *s)
{
return (s->top == max - 1) ? 1 : 0;
}
void push(STACK *s, int n)
{
if (isFull(s))
{
printf("\n The Stack is Full!");
}
else
{
s->top++;
s->item[s->top] = n;
}
}
void printStack(STACK *s)
{
int i;
for (i = 0; i <= s->top; i++)
{
printf("\t%d", s->item[i]);
}
}
int identical(STACK *s1, STACK *s2)
{
int flag = 0, i = 0;
while (i <= s1->top)
{
if (s1->item[i] == s2->item[i])
{
flag = 1;
}
else
{
flag = 0;
break;
}
i++;
}
return flag;
}
int main()
{
STACK s1, s2;
int choice, n;
initStack(&s1);
initStack(&s2);
do
{
printf("\n------------------");
printf("\n1.push(1)\n2.push(2)\n3.display(1)\n4.display(2)\n5.Exit");
printf("\n------------------");
printf("\n Enter your choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("\n Enter data for first stack insertion:");
scanf("%d", &n);
push(&s1, n);
break;
case 2:
printf("\n Enter data for second stack insertion:");
scanf("%d", &n);
push(&s2, n);
break;
case 3:
printf("\n The first stack is:\n");
printStack(&s1);
break;
case 4:
printf("\n The second stack is:\n");
printStack(&s2);
break;
}
} while (choice != 5);
if (identical(&s1, &s2))
{
printf("\n The Both stacks are identical!");
}
else
{
printf("\n The Both stacks are not identical!");
}
getch();
return 0;
}
------------------------------------------------------------------------------------------
2) Write a program that copies the contents of one stack into another. The order of two stacks
must be identical.(Hint: Use a temporary stack to preserve the order).
ANS:
#include <stdio.h>
#include <conio.h>
#define max 50
typedef struct stack
{
int top;
int item[max];
} STACK;
void initStack(STACK *ps)
{
ps->top = -1;
}
int isEmpty(STACK *ps)
{
if (ps->top == -1)
return 1;
else
return 0;
}
int isFull(STACK *ps)
{
if (ps->top == max - 1)
return 1;
else
return 0;
}
void push(STACK *ps, int n)
{
if (isFull(ps))
{
printf("\n Stack is full---");
}
else
{
ps->top++;
ps->item[ps->top] = n;
}
}
int pop(STACK *ps)
{
int x;
if (isEmpty(ps))
{
printf("\n Stack is Empty---");
}
else
{
x = ps->item[ps->top];
ps->top--;
}
return x;
}
void display(STACK *ps)
{
int i;
for (i = 0; i < ps->top; i++)
{
printf("\t %d", ps->item[i]);
}
}
int main()
{
STACK s1, s2, temp;
initStack(&s1);
initStack(&s2);
initStack(&temp);
int choice, n;
do
{
printf("\n ---------------------");
printf("\n1.push\n2.Exit");
printf("\n-----------------------");
printf("\n Enter choice:");
scanf("%d", &choice);
printf("\n Enter stack element:");
scanf("%d", &n);
push(&s1, n);
} while (choice != 2);
printf("\n The original stack is:\n");
display(&s1);
while (!isEmpty(&s1))
{
n = pop(&s1);
push(&temp, n);
}
while (!isEmpty(&temp))
{
n = pop(&temp);
push(&s2, n);
}
printf("\n The copied stack is:\n");
display(&s2);
getch();
return 0;
}
-------------------------------------------------------------------------------------
3) Write a ‘C’ program to accept an infix expression, convert it into its equivalent prefix
expression and display the result. (Use Static/Dynamic implementation of Stack).
ANS:
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <ctype.h>
#define max 50
typedef struct stack
{
int top;
int item[max];
} STACK;
void initStack(STACK *ps)
{
ps->top = -1;
}
int isEmpty(STACK *ps)
{
if (ps->top == -1)
return 1;
else
return 0;
}
int isFull(STACK *ps)
{
if (ps->top == max - 1)
return 1;
else
return 0;
}
void push(STACK *ps, char ch)
{
if (isFull(ps))
printf("\n Stack is full...");
else
{
ps->top++;
ps->item[ps->top] = ch;
}
}
char pop(STACK *ps)
{
char x;
if (isEmpty(ps))
printf("\n Stack is Empty...");
else
{
x = ps->item[ps->top];
ps->top--;
}
return x;
}
int main()
{
int i, j, len;
char infix[20], ch, prefix[20];
STACK s1;
initStack(&s1);
printf("\n Enter infix expression:");
scanf("%s", infix);
len = strlen(infix);
for (i = len - 1; i >= 0; i--)
{
if (isalnum(infix[i]))
{
prefix[j] = infix[i];
j++;
}
else
{
switch (infix[i])
{
case '*':
case '-':
case '+':
case '/':
case '%':
case ')':
push(&s1, infix[i]);
break;
case '(':
while ((ch = pop(&s1)) != ')')
{
prefix[j] = ch;
j++;
}
break;
}
}
}
while (!isEmpty(&s1))
{
prefix[j] = pop(&s1);
j++;
}
prefix[j] = '\0';
strcpy(prefix, strrev(prefix));
printf("\n The Prefix expression is:%s", prefix);
getch();
return 0;
}
--------------------------------------------------------------------------------
Comments
Post a Comment
Enter comment here!