Applications of Stack
1. Reverse a String Using Stack.
Algorithm:
1. Create an empty stack
2. One by one push all characters of string to stack
3. One by one pop all characters from stack and put them back to string.
2. One by one push all characters of string to stack
3. One by one pop all characters from stack and put them back to string.
Program Code:
#include <stdio.h>
#include <string.h>
#define max 100
int top,stack[max];
void push(char x){
// Push(Inserting Element in stack) operation
if(top == max-1){ printf("\n\t Stack overflow."); }
else { stack[++top]=x; }
}
void pop(){
// Pop (Removing element from stack)
printf("%c",stack[top--]);
}
int main()
{
char str[]="I LOVE MY INDIA";
int len = strlen(str);
int i;
for(i=0;i<len;i++)
push(str[i]);
for(i=0;i<len;i++)
pop();
return 0;
}
OUTPUT:
AIDNI YM EVOL I
-------------------------------------------------------------------------------------------------------------------
2. Conversion of Decimal to Binary number Using Stack.
Algorithm:
1. The given number is divided by 2 successively and remainders are pushed in stack. 2. Remainders are popped one at a time and converted into Binary.
Program Code:
// Decimal to Binary conversion using Stack
#include<stdio.h>
#include<math.h>
#define MAX 10
int top=-1, stack[MAX];
void push(int);
int pop(void);
int main()
{
int i,n,x,flag=0,s, bin=0, factor;
printf("\n\t Enter any decimal number: ");
scanf("%d",&n);
while(n>0)
{
if(n==1)
push(n);
else
{
x = n%2;
push(x);
}
n/=2;
flag++;
}
for(i=0;i<flag;i++)
{
s = pop();
bin = bin + s*pow(10,(flag-1-i));
}
printf("\n\t Equivalent Binary number=%d",bin);
}
void push(int n)
{
if(top == MAX-1)
{ printf("\n\tStack Overflow"); }
stack[++top] = n;
}
int pop(void)
{
int y;
if(top == -1)
{ printf("Satck Underflow"); }
y = stack[top];
top = top-1;
return y;
}
OUTPUT:
Enter any decimal number: 20
Equivalent Binary number=10100
------------------------------------------------------------------------------------
3. To check whether a given mathematical expression having nested parenthesis is Valid or Not Using Stack.
Program Code:
/* WAP to check validity of arithmetic expression containing nested parentheses using
stack */
#include<stdio.h>
#include<string.h>
#define MAX 30
#define TRUE 1
#define FALSE 0
int top=-1;
int stack[MAX];
void push(char);
char pop();
void main()
{
char expr[MAX],t;
int i,valid=TRUE;
printf("\n\t Enter an algebraic expression:");
gets(expr);
for(i=0;i<strlen(expr);i++)
{
if(expr[i]=='('||expr[i]=='{'||expr[i]=='[')
push(expr[i]);
if(expr[i]==')'||expr[i]=='}'||expr[i]==']')
if(top==-1) /* Stack Empty */
valid=FALSE;
else
{ t=pop();
if(expr[i]==')'&& (t=='{'||t=='['))
valid=FALSE;
if(expr[i]=='}'&& (t=='('||t=='['))
valid=FALSE;
if(expr[i]==']'&& (t=='('||t=='{'))
valid=FALSE;
}
}
if(top>=0)
valid=FALSE;
if(valid==TRUE)
printf("\n\t Valid Expression.");
else
printf("\n\t Invalid Expression.");
}
void push(char item)
{
if(top==(MAX-1))
printf("\n\t Stack Overflow.");
else
{
top=top+1;
stack[top]=item;
}
}
char pop()
{
if(top==-1)
printf("\n\t Stack Underflow.");
else
return(stack[top--]);
}
OUTPUT:
Enter an algebraic expression:(A+B)*C
Valid Expression.
------------------------------------------------------------------------------------------------------------------------
4. Conversion of Infix to Postfix Expression Using Stack.
Algorithm:
Step 1 : Scan the Infix Expression from left to right.
Step 2 : If the scanned character is an operand, append it to Postfix string.
Step 3 : Else,
Step 3.1 : If the precedence order of the scanned(incoming) operator is greater than the precedence order of the operator in the stack (or the stack is empty or the stack contains a ‘(‘ or ‘[‘ or ‘{‘), push it on stack.
Step 3.2 : Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.)
Step 4 : If the scanned character is an ‘(‘ or ‘[‘ or ‘{‘, push it to the stack.
Step 5 : If the scanned character is an ‘)’or ‘]’ or ‘}’, pop the stack and and output it until a ‘(‘ or ‘[‘ or ‘{‘ respectively is encountered, and discard both the parenthesis.
Step 6 : Repeat steps 2 to 6 until infix expression is scanned.
Step 7 : Print the output
Step 8 : Pop and output from the stack until it is not empty.
Program Code:
#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;
}
OUTPUT:
Enter the expression : a+b*c
a b c * +
--------------------------------------------------------------------------------------
5. Evaluation of Postfix Expression Using Stack.
Algorithm:
1. Create a stack to store operands.
2. Scan the given expression from left to right.
3. a) If the scanned character is an operand, push it into the stack.
b) If the scanned character is an operator, POP 2 operands from stack and perform operation and PUSH the result back to the stack.
4. Repeat step 3 till all the characters are scanned.
5. When the expression is ended, the number in the stack is the final result.
Program Code:
#include<stdio.h>
int stack[20];
int top = -1;
void push(int x)
{ stack[++top] = x; }
int pop()
{ return stack[top--]; }
int main()
{
char exp[20];
char *e;
int n1,n2,n3,num;
printf("\n\t Enter the expression:");
scanf("%s",exp);
e = exp;
while(*e != '\0')
{
if(isdigit(*e))
{
num = *e - 48;
push(num);
}
else
{
n1 = pop();
n2 = pop();
switch(*e)
{
case '+':
{
n3 = n1 + n2;
break;
}
case '-':
{
n3 = n2 - n1;
break;
}
case '*':
{
n3 = n1 * n2;
break;
}
case '/':
{
n3 = n2 / n1;
break;
}
}
push(n3);
}
e++;
}
printf("\n\t The result of expression %s = %d",exp,pop());
return 0;
}
OUTPUT:
Enter the expression:234*+
The result of expression 234*+ = 14
---------------------------------------------------------------------------------------------------------------------------
Important Video Links:
No comments: