Assignment 5 Stack
Set A
a) Perform the following operations using static implementation of stack
i. Accept n integers from user and push it into the stack.
ii. Pop the element from the stack and display it (Use isEmpty())
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int stack[MAX];
int top = -1;
// Check if stack is full
int isFull()
{
return (top == MAX - 1);
}
// Check if stack is empty
int isEmpty()
{
return (top == -1);
}
// Push operation
void push(int value)
{
if(isFull())
{
printf("Stack Overflow\n");
return;
}
stack[++top] = value;
}
// Pop operation
int pop()
{
if(isEmpty())
{
printf("Stack Underflow\n");
return -1;
}
return stack[top--];
}
// Display stack
void display()
{
int i;
if(isEmpty())
{
printf("Stack is Empty\n");
return;
}
printf("Stack Elements:\n");
for(i = top; i >= 0; i--)
printf("%d\n", stack[i]);
}
int main()
{
int n, i, value;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d integers:\n", n);
for(i = 0; i < n; i++)
{
scanf("%d", &value);
push(value);
}
printf("\nStack after Push:\n");
display();
value = pop();
if(value != -1)
printf("\nPopped Element = %d\n", value);
printf("\nStack after Pop:\n");
display();
return 0;
}
b) Perform the following operations using dynamic implementation of stack
i. Accept n integers from user and push it into the stack.
ii. Pop the element from the stack and display it.
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *top = NULL;
// Push operation
void push(int value)
{
struct node *newnode;
newnode = (struct node *)malloc(sizeof(struct node));
if(newnode == NULL)
{
printf("Stack Overflow\n");
return;
}
newnode->data = value;
newnode->next = top;
top = newnode;
}
// Pop operation
int pop()
{
struct node *temp;
int value;
if(top == NULL)
{
printf("Stack Underflow\n");
return -1;
}
temp = top;
value = temp->data;
top = top->next;
free(temp);
return value;
}
// Display stack
void display()
{
struct node *temp = top;
if(top == NULL)
{
printf("Stack is Empty\n");
return;
}
printf("Stack Elements:\n");
while(temp != NULL)
{
printf("%d\n", temp->data);
temp = temp->next;
}
}
int main()
{
int n, i, value;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d integers:\n", n);
for(i = 0; i < n; i++)
{
scanf("%d", &value);
push(value);
}
printf("\nStack after Push:\n");
display();
value = pop();
if(value != -1)
printf("\nPopped Element = %d\n", value);
printf("\nStack after Pop:\n");
display();
return 0;
}
Set B
a) Perform the following operations using implementation of stack (Static or dynamic)
i. Accept n integers from user and push it into the stack.
ii. Reverses a string of characters using stack and check weather given string is palindrome or not.
#include <stdio.h>
#include <string.h>
#define MAX 100
// Integer Stack
int stack[MAX];
int top = -1;
// Character Stack
char cstack[MAX];
int ctop = -1;
// Push integer
void push(int value)
{
if(top == MAX - 1)
{
printf("Stack Overflow\n");
return;
}
stack[++top] = value;
}
// Display integer stack
void displayStack()
{
int i;
printf("Stack Elements:\n");
for(i = top; i >= 0; i--)
printf("%d\n", stack[i]);
}
// Push character
void pushChar(char ch)
{
cstack[++ctop] = ch;
}
// Pop character
char popChar()
{
return cstack[ctop--];
}
int main()
{
int n, i, value;
char str[MAX], rev[MAX];
// Push integers
printf("Enter number of integers: ");
scanf("%d", &n);
printf("Enter %d integers:\n", n);
for(i = 0; i < n; i++)
{
scanf("%d", &value);
push(value);
}
printf("\nStack after Push:\n");
displayStack();
// Clear input buffer
getchar();
// Reverse string
printf("\nEnter a string: ");
gets(str);
int len = strlen(str);
for(i = 0; i < len; i++)
pushChar(str[i]);
for(i = 0; i < len; i++)
rev[i] = popChar();
rev[len] = '\0';
printf("Reversed String: %s\n", rev);
if(strcmp(str, rev) == 0)
printf("The given string is a Palindrome.\n");
else
printf("The given string is NOT a Palindrome.\n");
return 0;
}
b) Write a menu driven program to perform the following operations on stack
i. Convert an infix expression of the form (a*(b-c*d)/((a+d)/b)) into its equivalent postfix notation.
ii. Evaluation of postfix expression
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAX 100
char stack[MAX];
int top = -1;
// Stack operations for characters
void push(char x)
{
stack[++top] = x;
}
char pop()
{
return stack[top--];
}
char peek()
{
return stack[top];
}
int precedence(char ch)
{
switch(ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return 0;
}
// Infix to Postfix
void infixToPostfix(char infix[], char postfix[])
{
int i = 0, j = 0;
char ch;
while(infix[i] != '\0')
{
ch = infix[i];
if(isalnum(ch))
postfix[j++] = ch;
else if(ch == '(')
push(ch);
else if(ch == ')')
{
while(peek() != '(')
postfix[j++] = pop();
pop();
}
else
{
while(top != -1 && precedence(peek()) >= precedence(ch))
postfix[j++] = pop();
push(ch);
}
i++;
}
while(top != -1)
postfix[j++] = pop();
postfix[j] = '\0';
}
// Evaluate Postfix
int evaluatePostfix(char postfix[])
{
int st[MAX];
int t = -1;
int i, a, b;
for(i = 0; postfix[i] != '\0'; i++)
{
if(isdigit(postfix[i]))
st[++t] = postfix[i] - '0';
else
{
b = st[t--];
a = st[t--];
switch(postfix[i])
{
case '+':
st[++t] = a + b;
break;
case '-':
st[++t] = a - b;
break;
case '*':
st[++t] = a * b;
break;
case '/':
st[++t] = a / b;
break;
}
}
}
return st[t];
}
int main()
{
int choice;
char infix[MAX], postfix[MAX];
do
{
printf("\n----- MENU -----\n");
printf("1. Infix to Postfix\n");
printf("2. Evaluate Postfix\n");
printf("3. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch(choice)
{
case 1:
top = -1;
printf("Enter Infix Expression: ");
scanf("%s", infix);
infixToPostfix(infix, postfix);
printf("Postfix Expression: %s\n", postfix);
break;
case 2:
printf("Enter Postfix Expression: ");
scanf("%s", postfix);
printf("Result = %d\n", evaluatePostfix(postfix));
break;
case 3:
printf("Program Ended.\n");
break;
default:
printf("Invalid Choice!\n");
}
} while(choice != 3);
return 0;
}
No comments:
Post a Comment