Assignment 8: Applications of Stack
Set A
a)Write a program that reverses a string of characters. The function should use a stack library (cststack.h) of stack of characters using a static implementation of the stack.
Program
#include <stdio.h>
#include <string.h>
#include "cststack.h"
main()
{
char str[]="Data Structure";
printf("%s\n",str);
int len = strlen(str);
int i;
for(i=0;i<len;i++)
push(str[i]);
for(i=0;i<len;i++)
pop();
}
Library Function ( .h file )
NOTE: save file name as ' cststack.h'.
#define max 100
int top,stack[max];
void push(char x)
{
if(top == max-1){
printf("stack overflow");
} else {
stack[++top]=x;
}
}
void pop()
{
printf("%c",stack[top--]);
}
b)Write a program to convert an infix expression of the form (a*(b+c)*((d-a)/b)) into its equivalent postfix notation. Consider usual precedence’s of operators. Use stack library of stack of characters using static implementation.
#include<stdio.h>
#include<ctype.h>
char stack[100];
int top = -1;
void push(char x)
{
stack[++top] = x;
}
char pop()
{
if(top == -1)
return -1;
else
return stack[top--];
}
int priority(char x)
{
if(x == '(')
return 0;
if(x == '+' || x == '-')
return 1;
if(x == '*' || x == '/')
return 2;
return 0;
}
int main()
{
char exp[100];
char *e, x;
printf("Enter the expression : ");
scanf("%s",exp);
printf("\n");
e = exp;
while(*e != '\0')
{
if(isalnum(*e))
printf("%c ",*e);
else if(*e == '(')
push(*e);
else if(*e == ')')
{
while((x = pop()) != '(')
printf("%c ", x);
}
else
{
while(priority(stack[top]) >= priority(*e))
printf("%c ",pop());
push(*e);
}
e++;
}
while(top != -1)
{
printf("%c ",pop());
}return 0;
}
Set B
a) A postfix expression of the form ab+cd-*ab/ is to be evaluated after accepting the values of a, b, c and d. The value should be accepted only once and the same value is to be used for repeated occurrence of same symbol in the expression. Formulate the problem and write a C program to solve the problem by using stack
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#define SIZE 40
int pop();
void push(int);
char postfix[SIZE];
int stack[SIZE], top = -1;
int main()
{
int i, a, b, result, pEval;
char ch;
for(i=0; i<SIZE; i++)
{
stack[i] = -1;
}
printf("\nEnter a postfix expression: ");
scanf("%s",postfix);
for(i=0; postfix[i] != '\0'; i++)
{
ch = postfix[i];
if(isdigit(ch))
{
push(ch-'0');
}
else if(ch == '+' || ch == '-' || ch == '*' || ch == '/')
{
b = pop();
a = pop();
switch(ch)
{
case '+': result = a+b;
break;
case '-': result = a-b;
break;
case '*': result = a*b;
break;
case '/': result = a/b;
break;
case '%':result = a%b;
break;
}
push(result);
}
}
pEval = pop();
printf("\nThe postfix evaluation is: %d\n",pEval);
return 0;
}
void push(int n)
{
if (top < SIZE -1)
{
stack[++top] = n;
}
else
{
printf("Stack is full!\n");
exit(-1);
}
}
int pop()
{
int n;
if (top > -1)
{
n = stack[top];
stack[top--] = -1;
return n;
}
else
{
printf("Stack is empty!\n");
exit(-1);
}
}
b) Write a program that checks whether a string of characters is palindrome or not. The function should use a stack library (cststack.h) of stack of characters using a static implementation of the stack.
Program
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "cststack.h"
void main()
{
int i;
char s[MAX], b;
printf("Enter the String\n");
scanf("%s", s);
for (i = 0;s[i] != '\0';i++)
{
b = s[i];
push(b);
}
for (i = 0;i < (strlen(s) / 2);i++)
{
if (stack[top] == stack[front])
{
pop();
front++;
}
else
{
printf("%s is not a palindrome\n", s);
break;
}
}
if ((strlen(s) / 2) == front)
printf("%s is palindrome\n", s);
front = 0;
top = -1;
}
Library Function ( .h file )
NOTE: save file name as ' cststack.h'.
#define MAX 50
int top = -1, front = 0;
int stack[MAX];
void push(char);
void pop();
void push(char a)
{
top++;
stack[top] = a;
}
void pop()
{
top--;
}
Set C
a) Write a program that checks the validity of parentheses in any algebraic expression. The function should use a stack library (cststack.h) of stack of characters using a static implementation of the stack.
/*
* C Program to Check if Expression is correctly Parenthesized
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int top = -1;
char stack[100];
// function prototypes
void push(char);
void pop();
void find_top();
void main()
{
int i;
char a[100];
printf("enter expression\n");
scanf("%s", &a);
for (i = 0; a[i] != '\0';i++)
{
if (a[i] == '(')
{
push(a[i]);
}
else if (a[i] == ')')
{
pop();
}
}
find_top();
}
// to push elements in stack
void push(char a)
{
stack[top] = a;
top++;
}
// to pop elements from stack
void pop()
{
if (top == -1)
{
printf("expression is invalid\n");
exit(0);
}
else
{
top--;
}
}
// to find top element of stack
void find_top()
{
if (top == -1)
printf("\nexpression is valid\n");
else
printf("\nexpression is invalid\n");
}
b) Write a program to find all solutions to the four queens problem. Your program will need to be able to handle a search for a configuration that has no solution
No comments:
Post a Comment