SET A:
1) Write a C program to implement Static implementation of stack of
integers with following operation:
-Initialize(), push(), pop(), isempty(), isfull(), display()
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 20
typedef struct stack
{
int top;
int item[MAX];
} Stack;
void initStack(Stack *ps)
{
ps->top = -1;
printf("Initialize Stack :
\n");
}
int isEmpty(Stack *ps)
{
if (ps->top == -1)
{
return 1;
}
return 0;
}
int isFull(Stack *ps)
{
if (ps->top == MAX - 1)
return 1;
return 0;
}
void push(Stack *ps, int data)
{
if (isFull(ps))
{
printf("Stack is
Overflow !! \n");
}
else
{
ps->top++;
ps->item[ps->top] =
data;
printf("Pushed
!!\n");
}
}
int pop(Stack *ps)
{
int num;
if (isEmpty(ps))
{
printf("Stack is Empty
!!\n");
}
else
{
num =
ps->item[ps->top];
ps->top--;
}
return num;
}
void displayStack(Stack *ps)
{
int i = 0;
while (i != ps->top + 1)
{
printf("%d\t",
ps->item[i]);
i++;
}
}
int main()
{
Stack s;
initStack(&s);
push(&s, 4);
push(&s, 5);
push(&s, 10);
push(&s, 77);
printf("The Stack is :
!!\n");
displayStack(&s);
getch();
return 0;
}
=============================================================
2) Write a C program to implement Dynamic implementation of stack of
integers with following operation:
-Initialize(), push(), pop(), isempty(), display().
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data;
struct node *next;
} Node;
Node *initStack(Node *stack)
{
stack = NULL;
return stack;
}
Node *push(Node *stack, int num)
{
Node *new_node;
new_node = (Node
*)malloc(sizeof(Node));
if (!new_node)
{
printf("Memory not
allocated !! \n");
exit(1);
}
new_node->data = num;
new_node->next = NULL;
if (stack == NULL)
{
stack = new_node;
}
else
{
new_node->next = stack;
stack = new_node;
}
printf("Pushed !!\n");
return stack;
}
int isEmpty(Node *stack)
{
if (stack == NULL)
{
return 1;
}
return 0;
}
Node *pop(Node *stack)
{
int data;
Node *temp = stack;
if (isEmpty(stack))
{
printf("Stack is
underflow !!\n");
}
data = temp->data;
stack = temp->next;
free(temp);
printf("The popped element
is... %d\n", data);
return stack;
}
void display(Node *stack)
{
printf("Stack is
!!\n");
while (stack != NULL)
{
printf("%d\t",
stack->data);
stack = stack->next;
}
printf("\n");
}
int main()
{
Node *stack;
int choice, data;
stack = initStack(stack);
do
{
printf("-------------
Menu Bar -------------------------\n");
printf(" 1. Push\n 2.
Pop\n 3. display\n 4. Exit\n");
printf("--------------------------------------------------\n");
printf("Enter your
choice \n");
scanf("%d",
&choice);
switch (choice)
{
case 1:
printf("Enter the
element : ");
scanf("%d",
&data);
stack = push(stack,
data);
break;
case 2:
stack = pop(stack);
break;
case 3:
display(stack);
break;
case 4:
exit(1);
break;
default:
printf("Wrong Input
!!\n");
exit(1);
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
Static implementation stack :
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 30
typedef struct stack
{
int top;
char items[MAX];
} Stack;
void initStack(Stack *ps)
{
ps->top = -1;
}
int isFull(Stack *ps)
{
return (ps->top == MAX - 1)
? 1 : 0;
}
int isEmpty(Stack *ps)
{
return (ps->top == -1) ? 1
: 0;
}
void push(Stack *ps, char data)
{
if (isFull(ps))
{
printf("Stack is
Overflow !! \n");
}
else
{
ps->top++;
ps->items[ps->top] =
data;
}
// printf("Pushed
!!\n");
}
void printStack(Stack *ps)
{
int i = 0;
while (i <= ps->top)
{
printf("%c",
ps->items[i]);
i++;
}
}
char pop(Stack *ps)
{
char ch;
if (isEmpty(ps))
{
printf("Stack is
underflow !! \n");
}
else
{
ch =
ps->items[ps->top];
ps->top--;
}
return ch;
}
int main()
{
Stack s;
int n;
char str[MAX];
initStack(&s);
printf("Enter the input
string : \n");
gets(str);
for (int i = 0; i <=
strlen(str); i++)
{
if (str[i] != ' ')
{
push(&s, str[i]);
}
else
{
while
(!isEmpty(&s))
{
printf("%c", pop(&s));
}
printf(" ");
}
}
while (!isEmpty(&s))
{
printf("%c",
pop(&s));
}
getch();
return 0;
}
Dynamic implementation Stack :
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
struct stack
{
char data;
struct stack *next;
} *top = NULL;
void push(char ch)
{
struct stack *new_node;
new_node = (struct stack
*)malloc(sizeof(struct stack));
new_node->data = ch;
new_node->next = top;
top = new_node;
// printf("Pushed
!!\n");
}
void display(struct stack *ps)
{
while (ps != NULL)
{
printf("%c",
ps->data);
ps = ps->next;
}
}
int isEmpty()
{
return (top == NULL) ? 1 : 0;
}
char pop()
{
struct stack *temp;
char ch;
if (isEmpty())
{
printf("Stack is
underflow !! \n");
}
else
{
ch = top->data;
temp = top;
top = temp->next;
free(temp);
}
return ch;
}
int main()
{
char str[MAX];
printf("Enter the input
string : \n");
fgets(str, MAX, stdin);
printf("%s", str);
for (int i = 0; i <
strlen(str); i++)
{
if (str[i] != ' ')
{
push(str[i]);
}
else
{
while (!isEmpty())
{
printf("%c", pop());
}
printf(" ");
}
}
// while (!isEmpty())
// {
// printf("%c", pop());
// }
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).
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 30
typedef struct stack
{
int top;
char items[MAX];
} Stack;
void initStack(Stack *ps)
{
ps->top = -1;
printf("Initialized Stack
!!\n");
}
int isFull(Stack *ps)
{
return (ps->top == MAX - 1) ?
1 : 0;
}
int isEmpty(Stack *ps)
{
return (ps->top == -1) ? 1 :
0;
}
void push(Stack *ps, char data)
{
if (isFull(ps))
{
printf("Stack is
Overflow !! \n");
}
else
{
ps->top++;
ps->items[ps->top] =
data;
}
// printf("Pushed
!!\n");
}
void printStack(Stack *ps)
{
int i = 0;
while (i <= ps->top)
{
printf("%c",
ps->items[i]);
i++;
}
}
char pop(Stack *ps)
{
char ch;
if (isEmpty(ps))
{
printf("Stack is
underflow !! \n");
}
else
{
ch =
ps->items[ps->top];
ps->top--;
}
return ch;
}
int main()
{
char str[MAX];
char cpy[MAX];
int num, j;
Stack s1;
initStack(&s1);
printf("Enter the String to
check palindrome or not : \n");
gets(str);
for (int i = 0; i <
strlen(str); i++)
{
push(&s1, str[i]);
}
for (j = 0; j < strlen(str);
j++)
{
cpy[j] = pop(&s1);
}
cpy[j] = '\0';
num = strcmp(str, cpy);
if (num == 0)
{
printf("The String is
Palindrome !!\n");
}
else
{
printf("The String is
not Palindrome !!\n");
}
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).
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX 30
typedef struct stack
{
int top;
char items[MAX];
} Stack;
void initStack(Stack *ps)
{
ps->top = -1;
printf("Initialized Stack
!!\n");
}
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 data)
{
if (isFull(ps))
{
printf("Stack is Full
!!\n");
return;
}
else
{
ps->top++;
ps->items[ps->top] =
data;
}
// printf("%d pushed
!!\n", data);
}
char pop(Stack *ps)
{
char ch;
if (isEmpty(ps))
{
printf("Stack is Empty
!!\n");
}
else
{
ch =
ps->items[ps->top];
ps->top--;
}
return ch;
}
int postfixEvaluate(Stack *ps, char exp[])
{
int i, op1, op2, result;
char ch;
for (i = 0; i < strlen(exp);
i++)
{
ch = exp[i];
switch (ch)
{
case '1':
push(ps, 1);
break;
case '2':
push(ps, 2);
break;
case '3':
push(ps, 3);
break;
case '4':
push(ps, 4);
break;
case '5':
push(ps, 5);
break;
case '6':
push(ps, 6);
break;
case '7':
push(ps, 7);
break;
case '8':
push(ps, 8);
break;
case '9':
push(ps, 9);
break;
case '0':
push(ps, 0);
break;
case '+':
op2 = pop(ps);
op1 = pop(ps);
result = op1 + op2;
push(ps, result);
break;
case '-':
op2 = pop(ps);
op1 = pop(ps);
result = op1 - op2;
push(ps, result);
break;
case '*':
op2 = pop(ps);
op1 = pop(ps);
result = op1 * op2;
push(ps, result);
break;
case '/':
op2 = pop(ps);
op1 = pop(ps);
result = op1 / op2;
push(ps, result);
break;
}
}
return result;
}
int main()
{
Stack s;
int res;
char exp[MAX];
initStack(&s);
printf("Enter the postfix
expresion : ");
gets(exp);
res = postfixEvaluate(&s,
exp);
printf("Value of expresion
is : %d\n", res);
getch();
return 0;
}
=====================================================================
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).
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX 30
typedef struct stack
{
int top;
char items[MAX];
} Stack;
void initStack(Stack *ps)
{
ps->top = -1;
printf("Initialized Stack
!!\n");
}
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 data)
{
if (isFull(ps))
{
printf("Stack is Full
!!\n");
return;
}
else
{
ps->top++;
ps->items[ps->top] =
data;
}
// printf("%d pushed
!!\n", data);
}
char pop(Stack *ps)
{
char ch;
if (isEmpty(ps))
{
printf("Stack is Empty
!!\n");
}
else
{
ch =
ps->items[ps->top];
ps->top--;
}
return ch;
}
void infixToPostfix(Stack *ps, char exp[])
{
char postStr[MAX];
int i, j = 0;
char ch, data;
for (i = 0; exp[i] != '\0'; i++)
{
ch = exp[i];
if (isalnum(ch))
{
postStr[j++] = ch;
}
else
{
switch (ch)
{
case '(':
case '+':
case '-':
case '*':
case '/':
push(ps, ch);
break;
case ')':
while ((data =
pop(ps)) != '(')
{
postStr[j++] =
data;
}
break;
}
}
}
while (!isEmpty(ps))
{
postStr[j++] = pop(ps);
}
postStr[j] = '\0';
printf("Postfix string is :
%s", postStr);
}
int main()
{
Stack s;
char exp[MAX];
initStack(&s);
printf("Enter the infix
expresion : ");
gets(exp);
infixToPostfix(&s, exp);
getch();
return 0;
}
=====================================================================
SET C:
1) Write a program to check whether the contents of two stacks are
identical.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 30
typedef struct stack
{
int top;
char items[MAX];
} Stack;
void initStack(Stack *ps)
{
ps->top = -1;
printf("Initialized Stack
!!\n");
}
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 data)
{
if (isFull(ps))
{
printf("Stack is Full
!!\n");
return;
}
else
{
ps->top++;
ps->items[ps->top] =
data;
}
// printf("%d pushed
!!\n", data);
}
int pop(Stack *ps)
{
int t;
if (isEmpty(ps))
{
printf("Stack is Empty
!!\n");
}
else
{
t = ps->items[ps->top];
ps->top--;
}
return t;
}
int checkIdentical(Stack *ps1, Stack *ps2)
{
int flag = 1;
for (int i = 0; i <=
ps1->top; i++)
{
if (ps1->items[i] ==
ps2->items[i])
{
flag = 1;
}
else
{
return 0;
}
}
return flag;
}
int main()
{
Stack s1, s2;
int n, value, result;
initStack(&s1);
initStack(&s2);
printf("Enter the how many
elements : ");
scanf("%d", &n);
printf("Enter the elements
for First Stack : \n");
for (int i = 0; i < n; i++)
{
printf("Enter %d
position : ", i);
scanf("%d",
&value);
push(&s1, value);
}
printf("Enter the elements
for Second Stack : \n");
for (int i = 0; i < n; i++)
{
printf("Enter %d
position : ", i);
scanf("%d",
&value);
push(&s2, value);
}
result = checkIdentical(&s1,
&s2);
if (result > 0)
{
printf("The Both Stacks
are Identical !! \n");
}
else
{
printf("The Both Stacks
are not Identical !! \n");
}
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).
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 30
typedef struct stack
{
int top;
char items[MAX];
} Stack;
void initStack(Stack *ps)
{
ps->top = -1;
printf("Initialized Stack
!!\n");
}
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 data)
{
if (isFull(ps))
{
printf("Stack is Full
!!\n");
return;
}
else
{
ps->top++;
ps->items[ps->top] =
data;
}
// printf("%d pushed
!!\n", data);
}
int pop(Stack *ps)
{
int t;
if (isEmpty(ps))
{
printf("Stack is Empty
!!\n");
}
else
{
t = ps->items[ps->top];
ps->top--;
}
return t;
}
int checkIdentical(Stack *ps1, Stack *ps2)
{
int flag = 1;
for (int i = 0; i <=
ps1->top; i++)
{
if (ps1->items[i] ==
ps2->items[i])
{
flag = 1;
}
else
{
return 0;
}
}
return flag;
}
void copyStack(Stack *org, Stack *cpy)
{
for (int i = 0; i <=
org->top; i++)
{
push(cpy, org->items[i]);
}
}
void printStack(Stack *ps)
{
for (int i = 0; i <=
ps->top; i++)
{
printf("%d\t",
ps->items[i]);
}
printf("\n");
}
int main()
{
Stack s1, temp;
int n, data, value, j = 0;
initStack(&s1);
initStack(&temp);
printf("Enter the how many
elements : ");
scanf("%d", &n);
printf("Enter the elements
for First Stack : \n");
for (int i = 0; i < n; i++)
{
printf("Enter %d
position : ", i);
scanf("%d",
&value);
push(&s1, value);
}
copyStack(&s1, &temp);
// check both stack s1 and copy
are identical or not
if (checkIdentical(&s1,
&temp))
{
printf("Both Stack is
identical !!\n");
}
else
{
printf("Both Stack is
not identical !!\n");
}
printf("Original Stack is !!
\n");
printStack(&s1);
printf("After copied is
!!\n");
printStack(&temp);
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).
Static implementation :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX 30
typedef struct stack
{
int top;
char items[MAX];
} Stack;
void initStack(Stack *ps)
{
ps->top = -1;
printf("Initialized Stack
!!\n");
}
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 data)
{
if (isFull(ps))
{
printf("Stack is Full
!!\n");
return;
}
else
{
ps->top++;
ps->items[ps->top] =
data;
}
// printf("%d pushed
!!\n", data);
}
char pop(Stack *ps)
{
char ch;
if (isEmpty(ps))
{
printf("Stack is
Empty !!\n");
}
else
{
ch =
ps->items[ps->top];
ps->top--;
}
return ch;
}
void infixToPrefix(Stack *ps, char exp[])
{
int length = strlen(exp);
char prefix_str[MAX];
int i, j = 0;
char ch, data;
for (i = length - 1; i >=
0; i--)
{
ch = exp[i];
if (isalnum(ch))
{
push(ps, ch);
}
switch (ch)
{
case ')':
push(ps, ch);
break;
case '(':
while ((data =
pop(ps)) != ')')
{
prefix_str[j++] =
data;
}
break;
case '+':
case '-':
case '*':
case '/':
prefix_str[j++] = ch;
break;
}
}
while (!isEmpty(ps))
{
prefix_str[j++] = pop(ps);
}
prefix_str[j] = '\0';
printf("Prefix string :
%s", prefix_str);
}
int main()
{
Stack s;
char str[MAX];
initStack(&s);
printf("Enter the infix
expresion : ");
gets(str);
infixToPrefix(&s, str);
return 0;
}
-------------------
Dynamic implementation :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX 30
typedef struct stack
{
int data;
struct stack *next;
} Stack;
Stack *top; // Top mean stack this is global variable
void initStack(Stack *ps)
{
top = NULL;
printf("Initialized Stack
!!\n");
}
Stack *push(Stack *ps, char value)
{
Stack *new_node = NULL;
new_node = (Stack
*)malloc(sizeof(Stack));
new_node->data = value;
new_node->next = top;
top = new_node;
// printf("push :
%c\n", value);
return top;
}
int isEmpty(Stack *ps)
{
return (top == NULL) ? 1 : 0;
}
int pop(Stack *ps)
{
char t;
Stack *temp = top;
if (isEmpty(top))
{
printf("The Stack is
Empty !!");
return -1;
}
else
{
t = temp->data;
top = temp->next;
free(temp);
}
return t;
}
void infixToPrefix(Stack *ps, char str[])
{
int len = strlen(str);
int i, j = 0;
char ch, data, prefix[MAX];
for (i = len - 1; i >= 0;
i--)
{
ch = str[i];
if (isdigit(ch))
{
printf("Please
enter alphabets. Digit not allow!!\n");
break;
}
if (isalpha(ch))
{
top = push(top, ch);
}
switch (ch)
{
case '+':
case '-':
case '*':
case '/':
prefix[j++] = ch;
break;
case ')':
push(top, ch);
break;
case '(':
while ((data =
pop(top)) != ')')
{
prefix[j++] =
data;
}
break;
}
}
while (!isEmpty(top))
{
prefix[j++] = pop(top);
}
prefix[j] = '\0';
for (int j = 0; j <
strlen(prefix); j++)
{
printf("%c",
prefix[j]);
}
}
int main()
{
Stack s;
char str[MAX];
initStack(&s);
printf("Enter the infix
expresion : ");
fgets(str, MAX, stdin);
printf("%s", str);
infixToPrefix(&s, str);
return 0;
}
====================================================================
0 Comments