Exercise 5:
i) Implement a stack using arrays and linked lists.
// C Program for Stack using Arrays.
#include <stdio.h>
#include <stdlib.h>
#define SIZE 100
int stack[SIZE];
int top = -1;
void push(int element);
void pop();
void peek();
void display();
int main()
{
int choice,data;
while(1){
printf("------------------------------------\n");
printf(" STACK IMPLEMENTATION PROGRAM \n");
printf("------------------------------------\n");
printf("1. Push\n");
printf("2. Pop\n");
printf("3. Peek\n");
printf("4. Display\n");
printf("5. Exit\n");
printf("------------------------------------\n");
printf("Enter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1:
printf("Enter data to push into stack: ");
scanf("%d",&data);
push(data);
break;
case 2:
pop();
break;
case 3:
peek();
break;
case 4:
display();
break;
case 5:
exit(0);
default:
printf("Invalid choice, please try again.\n");
}
printf("\n\n");
}
return 0;
}
void push(int element)
{
if(top>=SIZE-1)
{
printf("Stack Overflow, can't add more elements to stack.\n");
return;
}
top++;
stack[top]=element;
printf("Data pushed to stack.\n");
}
void pop()
{
if(top==-1)
{
printf("Stack is empty.\n");
}
else
{
printf("%d popped from the stack\n",stack[top]);
top--;
}
}
void peek()
{
if(top==-1)
{
printf("Stack is empty.\n");
}
else
{
printf("%d peek from the stack\n",stack[top]);
}
}
void display()
{
int i;
if(top==-1)
{
printf("Stack is empty\n");
return;
}
for(i=top;i>=0;i--)
{
printf("%d\n",stack[i]);
}
}
// C Program for Stack using Linked list.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define CAPACITY 50
struct stack{
int data;
struct stack *next;
} *top=NULL;
int size=0;
void push(int element);
void pop();
void peek();
void display();
int main()
{
int choice,data;
while(1){
printf("------------------------------------\n");
printf(" STACK IMPLEMENTATION PROGRAM \n");
printf("------------------------------------\n");
printf("1. Push\n");
printf("2. Pop\n");
printf("3. Peek\n");
printf("4. Display\n");
printf("5. Exit\n");
printf("------------------------------------\n");
printf("Enter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter data to push into stack: ");
scanf("%d",&data);
push(data);
break;
case 2:
pop();
break;
case 3:
peek();
break;
case 4:
display();
break;
case 5:
exit(0);
default:
printf("Invalid choice, please try again.\n");
}
printf("\n\n");
}
return 0;
}
void push(int element)
{
if(size>=CAPACITY)
{
printf("Stack Overflow, can't add more element to stack.\n");
return;
}
struct stack *newNode=(struct stack*)malloc(sizeof(struct stack));
newNode->data=element;
newNode->next=top;
top=newNode;
size++;
printf("Data pushed to stack.\n");
}
void pop()
{
if(size<=0 || top==NULL){
printf("Stack is empty.\n");
return;
}
struct stack *topNode=top;
int data=top->data;
printf("%d popped from the stack\n",data);
top=top->next;
free(topNode);
size--;
}
void peek()
{
if(size<=0 || top==NULL)
{
printf("Stack is empty.\n");
return;
}
printf("%d peek from the stack\n",top->data);
}
void display()
{
struct stack *temp=top;
if(temp==NULL)
{
printf("stack is empty/underflow\n");
return;
}
printf("Stack elements\n");
while(temp!=NULL){
printf("%d\n",temp->data);
temp=temp->next;
}
}
ii) Write a program to evaluate a postfix expression using a stack
// C Program for postfix evaluation:
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAX 100
int stack[MAX];
int top=-1;
void push(int x)
{
if(top==MAX-1)
{
printf("Stack Overflow\n");
return;
}
stack[++top]=x;
}
int pop()
{
if(top==-1)
{
printf("Stack Underflow\n");
return -1;
}
return stack[top--];
}
int main()
{
char exp[100];
int i=0;
printf("Enter postfix expression: ");
fgets(exp,sizeof(exp),stdin);
exp[strcspn(exp,"\n")]='\0';
while(exp[i]!='\0')
{
if(exp[i]==' ')
{
i++;
continue;
}
if(isdigit(exp[i]))
{
int num=0;
while(isdigit(exp[i]))
{
num=num*10+(exp[i]-'0');
i++;
}
push(num);
}
else
{
int n1=pop();
int n2=pop();
switch(exp[i])
{
case '+': push(n2+n1); break;
case '-': push(n2-n1); break;
case '*': push(n2*n1); break;
case '/': push(n2/n1); break;
default:
printf("Invalid operator: %c\n",exp[i]);
return 1;
}
i++;
}
}
if(top==0)
printf("Result = %d\n",pop());
else
printf("Invalid Expression\n");
return 0;
}
iii) Implement a program to check for balanced parentheses using a stack.
// C Program to check balancing parentheses:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 100
char stack[MAX_SIZE];
int top=-1;
void push(char data)
{
if(top==MAX_SIZE-1)
{
printf("Overflow stack!\n");
return;
}
top++;
stack[top]=data;
}
char pop()
{
if(top==-1)
{
printf("Empty stack!\n");
return '\0';
}
char data=stack[top];
top--;
return data;
}
int is_matching_pair(char char1,char char2)
{
if(char1=='(' && char2==')') return 1;
else if(char1=='[' && char2==']') return 1;
else if(char1=='{' && char2=='}') return 1;
else return 0;
}
int isBalanced(char* text)
{
for(int i=0;i<strlen(text);i++)
{
if(text[i]=='(' || text[i]=='[' || text[i]=='{')
{
push(text[i]);
}
else if(text[i]==')' || text[i]==']' || text[i]=='}')
{
if(top==-1)
{
return 0;
}
else if(!is_matching_pair(pop(),text[i]))
{
return 0;
}
}
}
if(top==-1)
return 1;
else
return 0;
}
int main()
{
char text[MAX_SIZE];
printf("Input an expression in parentheses: ");
scanf("%s",text);
if(isBalanced(text))
printf("The expression is balanced.\n");
else
printf("The expression is not balanced.\n");
return 0;
}
Comments
Post a Comment