Applications of Stack in Data Structure

Applications of Stack

In a stack, only limited operations are performed because it is restricted data structure. The elements are deleted from the stack in the reverse order.

Following are the applications of stack:

1. Expression Evaluation
2. Expression Conversion
    i. Infix to Postfix
    ii. Infix to Prefix
    iii. Postfix to Infix
    iv. Prefix to Infix
3. Backtracking
4. Memory Management

Expression Representation

There are three popular methods used for representation of an expression:

InfixA + BOperator between operands.
Prefix+ ABOperator before operands.
PostfixAB +Operator after operands.


1. Conversion of Infix to Postfix

Algorithm for Infix to Postfix

Step 1: Consider the next element in the input.

Step 2: If it is operand, display it.

Step 3: If it is opening parenthesis, insert it on stack.

Step 4: If it is an operator, then
  • If stack is empty, insert operator on stack.
  • If the top of stack is opening parenthesis, insert the operator on stack
  • If it has higher priority than the top of stack, insert the operator on stack.
  • Else, delete the operator from the stack and display it, repeat Step 4.
Step 5: If it is a closing parenthesis, delete the operator from stack and display them until an opening parenthesis is encountered. Delete and discard the opening parenthesis.

Step 6: If there is more input, go to Step 1.

Step 7: If there is no more input, delete the remaining operators to output.

Example: Suppose we are converting 3*3/(4-1)+6*2 expression into postfix form.

Following table shows the evaluation of Infix to Postfix:

ExpressionStackOutput
3Empty3
**3
3*33
//33*
(/(33*
4/(33*4
-/(-33*4
1/(-33*41
)-33*41-
++33*41-/
6+33*41-/6
*+*33*41-/62
2+*33*41-/62
Empty33*41-/62*+

So, the Postfix Expression is 33*41-/62*+

Example: Program for Infix to Postfix Conversion

#include <stdio.h>
#include <ctype.h>
#define SIZE 50
char s[SIZE];
int top=-1;      
push(char elem)
{                       
    s[++top]=elem;
    return 0;
}
char pop()
{                      
    return(s[top--]);
}
int pr(char elem)
{                 
    switch(elem)
    {
        case '#': return 0;
        case '(': return 1;
        case '+':
        case '-': return 2;
        case '*':
        case '/': return 3;
    }
    return 0;
}
void main()
{                        
    char infx[50], pofx[50], ch, elem;
    int i=0, k=0;
    printf("\n\nEnter Infix Expression: ");
    scanf("%s",infx);
    push('#');
    while( (ch=infx[i++]) != '\0')
    {
        if( ch == '(') push(ch);
        else
            if(isalnum(ch)) pofx[k++]=ch;
            else
                if( ch == ')')
                {
                    while( s[top] != '(')
                        pofx[k++]=pop();
                    elem=pop();
                }
                else
                {       
                    while( pr(s[top]) >= pr(ch) )
                        pofx[k++]=pop();
                    push(ch);
                }
    }
    while( s[top] != '#')     
    pofx[k++]=pop();
    pofx[k]='\0';          
    printf("\n\n Given Infix Expression: %s  \n Postfix Expresssion: %s\n",infx,pofx);    
}


Output:

infix to postfix

2. Infix to Prefix

Algorithm for Infix to Prefix Conversion:

Step 1: Insert “)” onto stack, and add “(” to end of the A .

Step 2: Scan A from right to left and repeat Step 3 to 6 for each element of A until the stack is empty .

Step 3: If an operand is encountered, add it to B .

Step 4: If a right parenthesis is encountered, insert it onto stack .

Step 5: If an operator is encountered then,
             a. Delete from stack and add to B (each operator on the top of stack) which has same or higher precedence than the operator.
              b. Add operator to stack.

Step 6: If left parenthesis is encountered then ,
            a. Delete from the stack and add to B (each operator on top of stack until a left parenthesis is encountered).
            b. Remove the left parenthesis.

Step 7: Exit

Example: Program for Infix to Prefix Conversion

#include<stdio.h>
#include <conio.h>
#include <string.h>
#include <ctype.h>
#define MAX 50
struct infix
{
    char target[MAX] ;
    char stack[MAX] ;
    char *s, *t ;
    int top, l ;
} ;
void initinfix ( struct infix * ) ;
void setexpr ( struct infix *, char * ) ;
void push ( struct infix *, char ) ;
char pop ( struct infix * ) ;
void convert ( struct infix * ) ;
int priority ( char c ) ;
void show ( struct infix ) ;
void main( )
{
    struct infix q ;
    char expr[MAX] ;
    clrscr( ) ;
    initinfix ( &q ) ;
    printf ( "\nEnter an expression in infix form: " ) ;
    gets ( expr ) ;
    setexpr ( &q, expr ) ;
    convert ( &q ) ;
    printf ( "The Prefix expression is: " ) ;
    show ( q ) ;
    getch( ) ;
}
/* initializes elements of structure variable */
void initinfix ( struct infix *pq )
{
    pq -> top = -1 ;
    strcpy ( pq -> target, "" ) ;
    strcpy ( pq -> stack, "" ) ;
    pq -> l = 0 ;
}
/* reverses the given expression */
void setexpr ( struct infix *pq, char *str )
{
    pq -> s = str ;
    strrev ( pq -> s ) ;
    pq -> l = strlen ( pq -> s ) ;
    *( pq -> target + pq -> l ) = '\0' ;
    pq -> t = pq -> target + ( pq -> l - 1 ) ;
}
/* adds operator to the stack */
void push ( struct infix *pq, char c )
{
    if ( pq -> top == MAX - 1 )
        printf ( "\nStack is full.\n" ) ;
    else
    {
        pq -> top++ ;
        pq -> stack[pq -> top] = c ;
    }
}
/* pops an operator from the stack */
char pop ( struct infix *pq )
{
    if ( pq -> top == -1 )
    {
        printf ( "Stack is empty\n" ) ;
        return -1 ;
    }
    else
    {
        char item = pq -> stack[pq -> top] ;
        pq -> top-- ;
        return item ;
    }
}
/* converts the infix expr. to prefix form */
void convert ( struct infix *pq )
{
    char opr ;
    while ( *( pq -> s ) )
    {
        if ( *( pq -> s ) == ' ' || *( pq -> s ) == '\t' )
        {
            pq -> s++ ;
            continue ;
        }
        if ( isdigit ( *( pq -> s ) ) || isalpha ( *( pq -> s ) ) )
        {
            while ( isdigit ( *( pq -> s ) ) || isalpha ( *( pq -> s ) ) )
            {
                *( pq -> t ) = *( pq -> s ) ;
                pq -> s++ ;
                pq -> t-- ;
            }
        }
        if ( *( pq -> s ) == ')' )
        {
            push ( pq, *( pq -> s ) ) ;
            pq -> s++ ;
        }
        if ( *( pq -> s ) == '*' || *( pq -> s ) == '+' || *( pq -> s ) == '/' ||*( pq -> s ) == '%' || *( pq -> s ) == '-' || *( pq -> s ) == '$' )
        {
            if ( pq -> top != -1 )
            {
                opr = pop ( pq ) ;
                while ( priority ( opr ) > priority ( *( pq -> s ) ) )
                {
                    *( pq -> t ) = opr ;
                    pq -> t-- ;
                    opr = pop ( pq ) ;
                }
                push ( pq, opr ) ;
                push ( pq, *( pq -> s ) ) ;
            }
            else
                push ( pq, *( pq -> s ) ) ;
                pq -> s++ ;
        }
        if ( *( pq -> s ) == '(' )
        {
            opr = pop ( pq ) ;
            while ( opr != ')' )
            {
                *( pq -> t ) = opr ;
                pq -> t-- ;
                opr = pop ( pq ) ;
            }
            pq -> s++ ;
        }
    }
    while ( pq -> top != -1 )
    {
        opr = pop ( pq ) ;
        *( pq -> t ) = opr ;
        pq -> t-- ;
    }
    pq -> t++ ;
}
/* returns the priotity of the operator */
int priority ( char c )
{
    if ( c == '$' )
        return 3 ;
    if ( c == '*' || c == '/' || c == '%' )
        return 2 ;
    else
    {
        if ( c == '+' || c == '-' )
            return 1 ;
        else
            return 0 ;
    }
}
/* displays the prefix form of given expr. */
void show ( struct infix pq )
{
    while ( *( pq.t ) )
    {
        printf ( " %c", *( pq.t ) ) ;
        pq.t++ ;
    }
}


Output:

infix to prefix

3. Postfix to Infix

Following is an algorithm for Postfix to Infix conversion:

Step 1: While there are input symbol left.

Step 2: Read the next symbol from input.

Step 3: If the symbol is an operand, insert it onto the stack.

Step 4: Otherwise, the symbol is an operator.

Step 5: If there are fewer than 2 values on the stack, show error /* input not sufficient values in the expression */

Step 6: Else,
             a. Delete the top 2 values from the stack.
             b. Put the operator, with the values as arguments and form a string.
             c. Encapsulate the resulted string with parenthesis.
             d. Insert the resulted string back to stack.

Step 7: If there is only one value in the stack, that value in the stack is the desired infix string.

Step 8: If there are more values in the stack, show error /* The user input has too many values */

Example: Suppose we are converting efg-+he-sh-o+/* expression into Infix.

Following table shows the evaluation of Postfix to Infix:

efg-+he-sh-o+/*NULL
fg-+he-sh-o+/*“e”
g-+he-sh-o+/*“f”
“e”
-+he-sh-o+/*“g”
“f”
“e”
+he-sh-o+/*“f”-“g”
“e”
he-sh-o+/*“e+f-g”
e-sh-o+/*“h”
“e+f-g”
-sh-o+/*“e”
“h”
“e+f-g”
sh-o+/*“h-e”
“e+f-g”
h-o+/*“s”
“h-e”
“e+f-g”
-o+/*“h”
“s”
“h-e”
“e+f-g”
o+/*“h-s”
“h-e”
“e+f-g”
+/*“o”
“s-h”
“h-e”
“e+f-g”
/*“s-h+o”
“h-e”
“e+f-g”
*“(h-e)/( s-h+o)”
“e+f-g”
NULL“(e+f-g)* (h-e)/( s-h+o)”

So, the Infix Expression is (e+f-g)* (h-e)/(s-h+o)

Example: Program for Postfix to Infix conversion

#include <stdio.h>
#include <stdlib.h>
int top = 10;
struct node
{
    char ch;
    struct node *next;
    struct node *prev;
}  *stack[11];
typedef struct node node;
void push(node *str)
{
    if (top <= 0)
        printf("Stack is Full ");
    else
    {
        stack[top] = str;
        top--;
    }
}
node *pop()
{
    node *exp;
    if (top >= 10)
        printf("Stack is Empty ");
    else
        exp = stack[++top];
    return exp;
}
void convert(char exp[])
{
    node *op1,  *op2;
    node *temp;
    int i;
    for (i=0;exp[i]!='\0';i++)
    if (exp[i] >= 'a'&& exp[i] <= 'z'|| exp[i] >= 'A' && exp[i] <= 'Z')
    {
        temp = (node*)malloc(sizeof(node));
        temp->ch = exp[i];
        temp->next = NULL;
        temp->prev = NULL;
        push(temp);
    }
    else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/' || exp[i] == '^')
    {
        op1 = pop();
        op2 = pop();
        temp = (node*)malloc(sizeof(node));
        temp->ch = exp[i];
        temp->next = op1;
        temp->prev = op2;
        push(temp);
    }
}
void display(node *temp)
{
    if (temp != NULL)
    {
        display(temp->prev);
        printf("%c", temp->ch);
        display(temp->next);
    }
}
void main()
{
    char exp[50];
    clrscr();
    printf("Enter the postfix expression :");
    scanf("%s", exp);
    convert(exp);
    printf("\nThe Equivalant Infix expression is:");
    display(pop());
    printf("\n\n");
    getch();
}


Output:

postfix to infix

4. Prefix to Infix

Algorithm for Prefix to Infix Conversion

Step 1: The reversed input string is inserted into a stack -> prefixToInfix(stack)

Step 2: If stack is not empty,
            a. Temp -> pop the stack
            b. If temp is an operator,
                  Write a opening parenthesis “(“ to show -> prefixToInfix(stack)
                  Write temp to show -> prefixToInfix(stack)
                  Write a closing parenthesis “)” to show
            c. Else If temp is a space ->prefixToInfix(stack)
            d. Else, write temp to show if stack.top != space ->prefixToInfix(stack)

Example: Suppose we are converting /-bc+-pqr expression from Prefix to Infix.

Following table shows the evaluation of Prefix to Infix Conversion:

ExpressionStack
-bc+-pqrEmpty
/-bc+-pq“q”
“r”
/-bc+-“p”
“q”
“r”
/-bc+“p-q”
“r”
/-bc“p-q+r”
/-b“c”
“p-q+r”
/-“b”
“c”
“p-q+r”
/“b-c”
“p-q+r”
NULL“((b-c)/((p-q)+r))”

So, the Infix Expression is ((b-c)/((p-q)+r))

Example: Program for Prefix to Infix Conversion

#include <string.h>
#include <ctype.h>

char opnds[50][80], oprs[50];
int  topr=-1, topd=-1;
pushd(char *opnd)
{
    strcpy(opnds[++topd],opnd);
}
char *popd()
{
    return(opnds[topd--]);
}
pushr(char opr)
{
    oprs[++topr]=opr;
}
char popr()
{
    return(oprs[topr--]);
}
int empty(int t)
{
    if( t == 0) return(1);
    return(0);
}
void main()
{
    char prfx[50],ch,str[50],opnd1[50],opnd2[50],opr[2];
    int i=0,k=0,opndcnt=0;
    clrscr();
    printf("Enter Prefix Expression = ");
    gets(prfx);
    printf(" Given Prefix Expression is : %s\n",prfx);
    while( (ch=prfx[i++]) != '\0')
    {
        if(isalnum(ch))
        {
            str[0]=ch; str[1]='\0';
            pushd(str); opndcnt++;
            if(opndcnt >= 2)
            {
                strcpy(opnd2,popd());
                strcpy(opnd1,popd());
                strcpy(str,"(");
                strcat(str,opnd1);
                ch=popr();
                opr[0]=ch;opr[1]='\0';
                strcat(str,opr);
                strcat(str,opnd2);
                strcat(str,")");
                pushd(str);
                opndcnt-=1;
            }
        }
        else
        {
            pushr(ch);
            if(opndcnt==1)opndcnt=0;  /* operator followed by single operand*/
        }
    }
    if(!empty(topd))
    {
        strcpy(opnd2,popd());
        strcpy(opnd1,popd());
        strcpy(str,"(");
        strcat(str,opnd1);
        ch=popr();
        opr[0]=ch;opr[1]='\0';
        strcat(str,opr);
        strcat(str,opnd2);
        strcat(str,")");
        pushd(str);
    }
    printf(" Infix Expression: ");
    puts(opnds[topd]);
    getch();
}


Output:

prefix to infix
▲