Exercise 5:Stack Operation
5.1 Implement a stack using arrays and linked list
Stack using array
Program:
#include <stdio.h>
#define MAX 5
int stack[MAX];
int top = -1;
// Push
void push(int val) {
if (top == MAX - 1) {
printf("Stack Overflow\n");
} else {
top++;
stack[top] = val;
}
}
// Pop
void pop() {
if (top == -1) {
printf("Stack Underflow\n");
} else {
printf("Deleted element: %d\n", stack[top]);
top--;
}
}
//Display
void display() {
if (top == -1) {
printf("Stack is empty\n");
} else {
printf("Stack elements:\n");
for (int i = top; i >= 0; i--) {
printf("%d\n", stack[i]);
}
}
}
// Main
int main() {
push(10);
push(20);
push(30);
display();
pop();
display();
return 0;
}
STACK USING LINKED LIST
#include <stdio.h>
#include <stdlib.h>
// Structure
struct node {
int data;
struct node *next;
};
struct node *top = NULL;
// Push
void push(int val) {
struct node *newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = val;
newnode->next = top;
top = newnode;
}
// Pop
void pop() {
if (top == NULL) {
printf("Stack Underflow\n");
} else {
struct node *temp = top;
printf("Deleted element: %d\n", temp->data);
top = top->next;
free(temp);
}
}
// Display
void display() {
struct node *temp = top;
if (temp == NULL) {
printf("Stack is empty\n");
return;
}
printf("Stack elements:\n");
while (temp != NULL) {
printf("%d\n", temp->data);
temp = temp->next;
}
}
// Main
int main() {
push(10);
push(20);
push(30);
display();
pop();
display();
return 0;
}
Output:
5.2 WRITE A PROGRAM TO EVALUATE A POSTFIX EXPRESSION USING STACK
Program:
#include <stdio.h>
#include <ctype.h>
#include <math.h>
char stack[100];
int top = -1;
// Stack functions
void push(char x) {
stack[++top] = x;
}
char pop() {
return stack[top--];
}
// Precedence
int precedence(char x) {
if(x == '+' || x == '-') return 1;
if(x == '*' || x == '/') return 2;
if(x == '^') return 3;
return 0;
}
// Infix → Postfix
void infixToPostfix(char infix[], char postfix[]) {
int i, k = 0;
char x;
for(i = 0; infix[i]; i++) {
if(isalnum(infix[i])) {
postfix[k++] = infix[i];
}
else if(infix[i] == '(') {
push(infix[i]);
}
else if(infix[i] == ')') {
while((x = pop()) != '(')
postfix[k++] = x;
}
else {
while(top != -1 && precedence(stack[top]) >= precedence(infix[i]))
postfix[k++] = pop();
push(infix[i]);
}
}
while(top != -1)
postfix[k++] = pop();
postfix[k] = '\0';
}
// Evaluate Postfix
int evaluatePostfix(char postfix[]) {
int s[100], top2 = -1;
for(int i = 0; postfix[i]; i++) {
if(isdigit(postfix[i])) {
s[++top2] = postfix[i] - '0';
}
else {
int val1 = s[top2--];
int val2 = s[top2--];
switch(postfix[i]) {
case '+': s[++top2] = val2 + val1; break;
case '-': s[++top2] = val2 - val1; break;
case '*': s[++top2] = val2 * val1; break;
case '/': s[++top2] = val2 / val1; break;
case '^': s[++top2] = pow(val2, val1); break;
}
}
}
return s[top2];
}
int main() {
char infix[100], postfix[100];
printf("Enter Infix Expression: ");
scanf("%s", infix);
infixToPostfix(infix, postfix);
printf("Postfix Expression: %s\n", postfix);
int result = evaluatePostfix(postfix);
printf("Result = %d\n", result);
return 0;
}
5.3 implement a program to check for balanced parantheses using stack
Program:
#include <stdio.h>
#include <string.h>
#define MAX 100
char stack[MAX];
int top = -1;
// Push
void push(char ch)
{
stack[++top] = ch;
}
// Pop
char pop()
{
if (top == -1)
return '\0';
return stack[top--];
}
// Check matching pair
int isMatchingPair(char open, char close) {
if (open == '(' && close == ')') return 1;
if (open == '{' && close == '}') return 1;
if (open == '[' && close == ']') return 1;
return 0;
}
// Check Balanced
int isBalanced(char exp[]) {
int i;
char ch;
for (i = 0; exp[i] != '\0'; i++) {
ch = exp[i];
// If opening bracket → push
if (ch == '(' || ch == '{' || ch == '[') {
push(ch);
}
// If closing bracket → pop and match
else if (ch == ')' || ch == '}' || ch == ']') {
if (top == -1)
return 0; // unbalanced
char popped = pop();
if (!isMatchingPair(popped, ch))
return 0; // mismatch
}
}
// If stack empty → balanced
if (top == -1)
return 1;
else
return 0;
}
// Main
int main() {
char exp[100];
printf("Enter expression: ");
scanf("%s", exp);
if (isBalanced(exp))
printf("Expression is Balanced\n");
else
printf("Expression is NOT Balanced\n");
return 0;
}
Output1:
Output2: