Exercise 7:
i) Use a stack to evaluate an infix expression and convert it to postfix.
// C Program for Conversion of Infix to Postfix using Stack.
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
char stk[20];
int top = -1;
int isEmpty()
{
return top == -1;
}
int isFull()
{
return top == MAX - 1;
}
char peek()
{
return stk[top];
}
char pop()
{
if (isEmpty())
return -1;
char ch = stk[top];
top--;
return ch;
}
void push(char oper)
{
if (isFull())
printf("Stack Full!!!!");
else
{
top++;
stk[top] = oper;
}
}
int checkIfOperand(char ch)
{
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
int precedence(char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
int covertInfixToPostfix(char *expression)
{
int i, j;
for (i = 0, j = -1; expression[i]; ++i)
{
if (checkIfOperand(expression[i]))
{
expression[++j] = expression[i];
}
else if (expression[i] == '(')
{
push(expression[i]);
}
else if (expression[i] == ')')
{
while (!isEmpty() && peek() != '(')
{
expression[++j] = pop();
}
if (!isEmpty() && peek() != '(')
return -1; // invalid expression
else
pop();
}
else // operator
{
while (!isEmpty() && precedence(expression[i]) <= precedence(peek()))
{
expression[++j] = pop();
}
push(expression[i]);
}
}
while (!isEmpty())
{
expression[++j] = pop();
}
expression[++j] = '\0';
printf("%s", expression);
}
int main()
{
char expression[] = "((a+(b*c))-d)";
covertInfixToPostfix(expression);
return 0;
}
ii) Create a program to determine whether a given string is a palindrome or not.
// C Program to check a String is Palindrome or not using Stack:
#include <stdio.h>
#include <string.h>
#define MAX 100
char stack[MAX];
int top = -1;
// Push operation
void push(char ch)
{
stack[++top] = ch;
}
// Pop operation
char pop()
{
return stack[top--];
}
int main()
{
char str[MAX];
int i, length;
int isPalindrome = 1;
printf("Enter a string: ");
scanf("%s", str);
length = strlen(str);
// Push all characters into stack
for (i = 0; i < length; i++)
{
push(str[i]);
}
// Compare original string with popped elements
for (i = 0; i < length; i++)
{
if (str[i] != pop())
{
isPalindrome = 0;
break;
}
}
if (isPalindrome)
printf("Palindrome");
else
printf("Not Palindrome");
return 0;
}
Double Ended Queue - Output Restricted Deque..
// C Program Output Restricted Deque:
#include <stdio.h>
#define size 5
int deque[size];
int f = -1, r = -1;
// insert_front function
void insert_front(int x)
{
if ((f == 0 && r == size - 1) || (f == r + 1))
{
printf("Overflow");
}
else if ((f == -1) && (r == -1))
{
f = r = 0;
deque[f] = x;
}
else if (f == 0)
{
f = size - 1;
deque[f] = x;
}
else
{
f = f - 1;
deque[f] = x;
}
}
// insert_rear function
void insert_rear(int x)
{
if ((f == 0 && r == size - 1) || (f == r + 1))
{
printf("Overflow");
}
else if ((f == -1) && (r == -1))
{
f = r = 0;
deque[r] = x;
}
else if (r == size - 1)
{
r = 0;
deque[r] = x;
}
else
{
r++;
deque[r] = x;
}
}
// display function
void display()
{
if ((f == -1) && (r == -1))
{
printf("\nDeque is empty");
return;
}
int i = f;
printf("\nElements in a deque are: ");
while (i != r)
{
printf("%d ", deque[i]);
i = (i + 1) % size;
}
printf("%d", deque[r]);
}
// getfront function
void getfront()
{
if ((f == -1) && (r == -1))
{
printf("\nDeque is empty");
}
else
{
printf("\nFront element: %d", deque[f]);
}
}
// getrear function
void getrear()
{
if ((f == -1) && (r == -1))
{
printf("\nDeque is empty");
}
else
{
printf("\nRear element: %d", deque[r]);
}
}
// delete_front function
void delete_front()
{
if ((f == -1) && (r == -1))
{
printf("\nDeque is empty");
}
else if (f == r)
{
printf("\nDeleted element: %d", deque[f]);
f = r = -1;
}
else if (f == size - 1)
{
printf("\nDeleted element: %d", deque[f]);
f = 0;
}
else
{
printf("\nDeleted element: %d", deque[f]);
f = f + 1;
}
}
// delete_rear function
void delete_rear()
{
if ((f == -1) && (r == -1))
{
printf("\nDeque is empty");
}
else if (f == r)
{
printf("\nDeleted element: %d", deque[r]);
f = r = -1;
}
else if (r == 0)
{
printf("\nDeleted element: %d", deque[r]);
r = size - 1;
}
else
{
printf("\nDeleted element: %d", deque[r]);
r = r - 1;
}
}
int main()
{
insert_front(10);
insert_front(20);
insert_rear(30);
insert_rear(40);
insert_rear(50);
display();
getfront();
getrear();
delete_front();
delete_rear();
display();
delete_rear();
display();
return 0;
}
iii) Implement a stack or queue to perform comparison and check for symmetry.
// C Program to check for Symmetry (Palindrome) using Double Ended Queue (Deque):
#include <stdio.h>
#include <ctype.h>
#define MAX_SIZE 100
char data[MAX_SIZE];
int front = -1;
int rear = -1;
// Function prototypes
void insertFront(char item);
void insertRear(char item);
char deleteFront();
char deleteRear();
int isEmpty();
// Insert element at the front of deque
void insertFront(char item)
{
if ((front == 0 && rear == MAX_SIZE - 1) || (front == rear + 1))
{
printf("Deque is full. Cannot insert at front.\n");
return;
}
if (front == -1)
{
front = rear = 0;
}
else if (front == 0)
{
front = MAX_SIZE - 1;
}
else
{
front = front - 1;
}
data[front] = item;
}
// Insert element at the rear of deque
void insertRear(char item)
{
if ((front == 0 && rear == MAX_SIZE - 1) || (front == rear + 1))
{
printf("Deque is full. Cannot insert at rear.\n");
return;
}
if (front == -1)
{
front = rear = 0;
}
else if (rear == MAX_SIZE - 1)
{
rear = 0;
}
else
{
rear = rear + 1;
}
data[rear] = item;
}
// Delete element from the front of deque
char deleteFront()
{
if (isEmpty())
{
printf("Deque is empty. Cannot delete from front.\n");
return '\0';
}
char item = data[front];
if (front == rear)
{
front = rear = -1;
}
else
{
front = (front + 1) % MAX_SIZE;
}
return item;
}
// Delete element from the rear of deque
char deleteRear()
{
if (isEmpty())
{
printf("Deque is empty. Cannot delete from rear.\n");
return '\0';
}
char item = data[rear];
if (front == rear)
{
front = rear = -1;
}
else if (rear == 0)
{
rear = MAX_SIZE - 1;
}
else
{
rear = rear - 1;
}
return item;
}
// Check if deque is empty
int isEmpty()
{
return (front == -1);
}
// Function to check if a string is palindrome
int isPalindrome(char *str)
{
front = rear = -1;
int i = 0;
while (str[i] != '\0')
{
if (isalnum(str[i]))
{
insertRear(tolower(str[i]));
}
i++;
}
while (front != rear && front != rear + 1)
{
char frontChar = deleteFront();
char rearChar = deleteRear();
if (frontChar != rearChar)
{
return 0; // Not palindrome
}
}
return 1; // Palindrome
}
int main()
{
char str[MAX_SIZE];
printf("Enter a string: ");
fgets(str, MAX_SIZE, stdin);
if (isPalindrome(str))
{
printf("The string \"%s\" is a palindrome.", str);
}
else
{
printf("The string \"%s\" is not a palindrome.", str);
}
return 0;
}
Comments
Post a Comment