Applications of Stack

Stack is one of the most useful data structure and is used in problems like Expression Evaluation, Backtracking, Memory Management and algorithms like Breadth First Search (BFS).

We have explored the applications of Stack in depth.

Stack is a data structure used to for data storage(like linked lists). It is an ordered list in which insertion and deletion is performed from one end. The order may be LIFO(Last In First Out) or FILO(First In Last Out). It mainly has 2 primary operations:

• push, which inserts the element in stack and
• pop, which removes the most recently added element from the stack.

Why Stack?

As discussed above Stack is a linear data structure used to store some data. So what is different about it?
Stack is an abstract data type which, unlike an array, can contain elements of different data types.
When we talk about storage, it's not fixed and is dynamic which is quite the opposite for arrays as they cannot be resized.Hence using the abstract data types such as Stack can surely give us an upper hand.

Applications of Stack

• Expression Evaluation
• Backtracking
• Memory Management

Expression Evaluation

There are mainly 3 methods which is used for evalauting the expression.

• Infix
• Prefix
• Postfix

Let us understand about their working by evaluating some simple arithematic expressions.

Infix expression is difficult to parse by the computers.Hence we convert it into either Prefix or Postfix notation for the evaluation purposes.
Let us see how the conversion works.

• Infix to Postfix

• Algorithm

1. Create a stack for each character, let's say 'X', for each character in the input stream
   1. if(X is an operand),
      output X
      [end of if]
   2. else if(X is a right parenthesis),
      pop the output tokens until a left parenthesis is popped(but not output)
      [end of else if]
   3. else(when X is a left parenthesis or an operator),
      pop the output tokens until one of the lower priority is encountered or when the stack becomes empty
      [end of else]
2. Pop and output token until the stack is empty
   For better understanding let us trace out an example: A* B-(C+D)+E
   Example

Input Infix Expression: A* B-(C+D)+E
Equivalent Postfx Expression: AB* CD+-E+

Code for infix to postfix using stack stl

#include<iostream> 
#include<stack>
#include<algorithm>
#include<string>
using namespace std; 

bool IsOperator(char c)
{
if(c=='+'||c=='-'||c=='*'||c=='/'||c=='^')
{
return True;
}
else
{
return False;
}
}                                 
int OpPrecedence(char c)  //Function to return precedence of operators
{ 
  if(c == '^') 
  return 3; 
  else if(c == '*' || c == '/') 
  return 2; 
  else if(c == '+' || c == '-') 
  return 1; 
return 0; 
} 

// The main function to convert infix expression 
//to postfix expression 
void infixToPostfix(string s,stack <char> ch) 
{
  int l = s.length(); 
  string ns; 
  for(int i = 0; i < l; i++) 
  {
if((infix[i] >= 'a' && infix[i] <= 'z')||(infix[i] >= 'A' && infix[i] <= 'Z'))
      {
 postfix+=infix[i]; // If the scanned character is an operand, add it to output 
      }
else if(infix[i] == '(')// If scanned char is '(' , push it into stack
       {
   ch.push(infix[i]);
       }
else if(infix[i] == ')')
{
   while((s.top()!='(') && (!s.empty()))//If scanned char is ')', pop until ')'
       {                                // is encountered
       char t=ch.top();
       postfix+=t;
       ch.pop();
       }
}
if(ch.top()=='(')
   {
    ch.pop();
   }
}

else if(IsOperator(infix[i])) //to check if scanned char is an operator and pop it
   {
       if(ch.empty())
       {
       ch.push(infix[i]);
       }
      else
       {
       if(precedence(infix[i])>precedence(ch.top()))
       {
       ch.push(infix[i]);
       } 
       else if((OpPrecedence(infix[i])==OpPrecedence(s.top()))&&(infix[i]=='^'))
       {
       ch.push(infix[i]);
       }
       else
       {
       while((!ch.empty())&&( OpPrecedence(infix[i])<=OpPrecedence(s.top())))
       {
       postfix+=ch.top();
       ch.pop();
       }
       ch.push(infix[i]);
       }
      }
     }
    }
      
      
  while(!ch.empty()) //pop all the elements
   {
   postfix+=ch.top();
   ch.pop();
   }

return postfix;
}
  



int main() 
{ 
  string inf, post;
	cout<<"Enter a Infix Expression :"<<endl;
	cin>>inf;
	stack <char> ch;
cout<<"INFIX EXPRESSION: "<<inf<<endl;
	post = InfixToPostfix(ch, inf);
	cout<<endl<<"POSTFIX EXPRESSION: "<<post;
 
return 0; 
} 

• Infix to Prefix
• Algorithm

1. Reverse the infix expression.
2. Examine the next element in the input.
3. If it is an operand, add it to the output expression.
4. If it is ')', top of the stack is popped and added to the expression until '(' is encountered.
5. If it is an operator then,
   1. If the operator has a higher priority than the operator at the top of stack,
      then the operator being scanned is pushed back
   2. If the precedence of the symbol being scanned is lower than or equal to the precedence of the symbol at the top of the stack, the stack is popped to the output.
6. Repeatedly pop from Stack and push each operator on the top of Stack until a left parenthesis is encountered.
7. Reverse the obtained prefix expression.
8. END.

• Example

Infix Expression: A+B*(C^ D - E)
Reverse Brackets : )E-D^C(* B +A
Reverse Expression : (E-D^C)* B+A

Reversing the final expression we get :+A* B-^CDE

Input Infix Expression: A+B*(C^ D - E)
Equivalent Prefix Expression: +A* B-^CDE

• Code for infix to prefix using stack stl

#include <iostream> 
#include<stack>
#include<algorithm>
#include<string>
using namespace std; 
 
bool IsOperator(char ch)        //to check for a valid operator
{ 
   if(ch == '+'||ch == '-'||ch == '*'||ch == '^'||ch == '^')
       return true;
   else
       return false;
} 
 
int OpPrecedence(char ch) 
{ 
   if (ch == '^') 
       return 3; 
   else if (ch == '*' || ch == '/') 
       return 2; 
   else if(ch == '-' || ch == '+')  
       return 1;
   return 0; 
} 
 
string InfixToPrefix(string infix, stack <char> s) 
{ 
   string prefix;
   int l = infix.size(); 
   reverse(infix.begin(), infix.end()); //reversing prefix expression
   
   
   for (int i = 0; i < l; i++) {
       if (infix[i] == '(') {
           infix[i] = ')';
       }
       else if (infix[i] == ')') {
           infix[i] = '(';
       }
   for (int i = 0; i < l; i++) //if operator is an operand then add it 
                                            //to the output
   {
 if ((infix[i] >= 'a' && infix[i] <= 'z') || (infix[i] >= 'A' && infix[i] <= 'Z')) 
       {
           prefix += infix[i];
       }
       else if (infix[i] == '(')    // If the traversed character is an '(', push
       {                             // it into stack
           s.push(infix[i]);
       }
       
       
        else if (infix[i] == ')') // If the traversed character is ')', pop from
                                  //stack until '(' is encountered
        {
           while ((s.top() != '(') && (!s.empty()))
           {
               prefix += s.top();
               s.pop();
           }
           if (s.top() == '(')  //remove '(' from stack
           {
               s.pop();
           }
         }
         
          else if (IsOperator(infix[i]))
          {
           if (s.empty())
           {
               s.push(infix[i]); //push current operator in stack
           }
           else 
           {
               if (OpPrecedence(infix[i]) > OpPrecedence(s.top()))
               {
                   s.push(infix[i]);  //push current operator in stack
               }
            else if ((OpPrecedence(infix[i]) == OpPrecedence(s.top()))
                   && (infix[i] == '^'))
                   {
                   while ((OpPrecedence(infix[i]) == OpPrecedence(s.top()))
                       && (infix[i] == '^'))
                   {
                       prefix += s.top();
                       s.pop();
                   }
                   s.push(infix[i]);   //push current operator in stack
              }
              
              
               else if (OpPrecedence(infix[i]) == OpPrecedence(s.top()))
               {
                   s.push(infix[i]);
               }
               else
               {
        while ((!s.empty()) && (OpPrecedence(infix[i]) < OpPrecedence(s.top())))
                   {
                       prefix += s.top();
                       s.pop();
                   }
                   s.push(infix[i]);
               }
           }
       }
   }
   
 
 while (!s.empty()) //popping the characters from stack 
 {
       prefix += s.top();
       s.pop();
   }

   reverse(prefix.begin(), prefix.end()); //reversing the prefix expression 
   return prefix;
}


int main()
{

   string in, pre;
   cout << "Enter a Infix Expression :" << endl;
   cin >> in;
   stack<char> ch;
   cout << "infix expression " << in << endl;
   prefix = InfixToPrefix(ch, in);
   cout << endl
        << "prefix expression " << prefix;

   return 0;
}
 

Backtracking

So let us first understand what backtracking is:
Backtracking is an improvement to Brute-force approach.It systematically searches for 1 possible solution from the given possible options. If we are able to find an optimized solution with the selected option then it becomes our final solution else we backtrack and choose a different option and try solving with it. If all the possible options are worked out then we claim that there is no solution to the problem.
Backtracking is also a form of recursion.

Here we will see the functioning of N-Queen Problem to comprehend backtracking clearly.

• N-Queen Problem

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.
Let us take an example for 4-Queen Problem.

• Algorithm

1. Start in the leftmost column
2. If all queens are placed return true
3. Try all rows in the current column. Do following for every tried row.
   1. If the queen can be placed safely in this row then mark this [row,column] as part of the solution and recursively check if placing queen here leads to a solution.
   2. If placing queen in [row, column] leads to a solution then return true.
   3. If placing queen doesn't lead to a solution then mark this [row, column] (Backtrack) and go to step (3.1) to try other rows.
4. If all rows have been tried and nothing worked, return false to trigger backtracking.

• Code

    
#include<iostream>
#define N 4
using namespace std;
 
void printBoard(int board[N][N])
{
   for (int i = 0; i < N; i++)
   {
      for (int j = 0; j < N; j++)
         cout << board[i][j] << " ";
         cout << endl;
    }
 }
 
 
 
 bool isValid(int board[N][N], int r, int c)
 {
   for (int i = 0; i < col; i++)  //check whether there is queen in the left or not
      if (board[r][i])
         return false;
   for (int i=r, j=c; i>=0 && j>=0; i--, j--)
      if (board[i][j]) //check whether there is queen in the left upper diagonal              return false;
   for (int i=row, j=col; j>=0 && i<N; i++, j--)
      if (board[i][j]) //check whether there is queen in the left lower diagonal
         return false;
   return true;
}

bool solnNQueen(int board[N][N], int c)
{
   if (c >= N) //when N queens are placed successfully
      return true;
   for (int i = 0; i < N; i++) //for each row, check if placing of queen is possible 
   {
      if (isValid(board, i, c) )
      {
         board[i][col] = 1; //if validate, place the queen at place (i, column)
         if ( solveNQueen(board, c + 1)) //Go for the other columns recursively
            return true;
         board[i][c] = 0; //When no place is vacant remove that queen
      }
   }
   return false;      /* If queen can not be place in any row in this column
                        then return false */
}

bool validSolution()
{
   int board[N][N];
   for(int i = 0; i<N; i++)
   for(int j = 0; j<N; j++)
   board[i][j] = 0;    //set all elements to 0
   
   if ( solnNQueen(board, 0) == false )  //starting from 0th column
   {
      cout << "Solution does not exist";
      return false;
   }
   printBoard(board);
   return true;
}
 
int main()
{
   validSolution();
}

Memory Management

Stacks in computing architectures are regions of memory where data is added or removed in a last-in-first-out (LIFO) manner.The operating system allocates memory segment for stack which includes arguments,the return value and local variable of a function. Stack variable will exist only until the function created them is running and after that they are all popped out of the stack and data is lost forever. Reading and writing from stack variable is very fast as the CPU organizes the memory very efficiently.Allocation and deallocation is an automatic process.

Complexity

Since the expression evaluation works on push() and pull() functions of stack
Complexity for push function: O(n)
Complexity for pull function: O(1)
which gives an overall complexity of O(n)

• Infix-Postfix: O(n)
• Infix-Prefix: O(n)
• N-Queen Problem: O(n!)

Applications

Some standard applications of stack are:

• Parenthesis balancing
  Opening parenthesis are pushed and when a closing parenthesis is encountered, pop the stack. If all the symbols are popped and no character is left unscanned, we
  can say that parenthesis are balanced.

• Used in Recursion
  Stack is used to store and restore recursive function along with it's argument(s).
  The data is stored from top to bottom in the stack.

• Undo Mechanism
  This mechanism is also performed with the help of stack.So stack stores the
  history of user mechanisms, and if a new action is performed it is added to the
  top of the stack. So an undo mechanism does nothing but pops the item from
  the stack.

• Reversing of a String
  Reading a string means pushing the items into the stack and reversing is just the
  pop operation. The last item will be on the top(LIFO) hence after popping them one
  by one we get a string in reverse order.

• Managing Function calls and Return mechanism
  Everytime a function is called it is pushed back into the stack along with the
  return address.When function is returned, it is first popped out of the stack
  and then the control is transferred to the return address(from where the function
  was called).

• Finding path in roadmap from one point to another
  Generally it is an application of backtracking.The key to backtracking being:
  each choice or decision is recorded in the stack and when we run out of decisions,
  the stack is popped and continue try for different choices for the previous
  decisions (here to find a minimum distance path between two points).

Parenthesis balancing

Parenthesis balancing is one of the major concept used in syntax highlighting editors. So let's take a quick look at the algorithm of how it is implemented
using stack.

• Algorithm

1. Scan the expression from left to right
2. If the character is an open bracket like '{','(','[', then push it back to
   stack.
3. If the scanned character is a closing bracket like '}',')',']' ,then pop from the stack and check if the popped character is same as the starting bracket of the string.
   If it is then the paranthesis is balanced otherwise iunbalanced

• Code using stack stl

#include<iostream>
#include<stack>
#include<string>
using namespace std;
bool IsBalanced(string s)
{
stack <char> stk;
string open="[{(";
char temp;
for(int i=0;i<s.length();i++)
{
  if(open.find(s[i])>=0)  //find returns the index of first occurance of the                                   //character in the given string
  {
      stk.push(s[i]);
  }

  if(stk.empty()) //should have the opening parenthesis
      return False;

  switch(s[i])
  {
      case ')':
      {
          temp=stk.top();
          stk.pop();
          if(temp!='(')
              return False;
          break;
      }
      case '}':
      {
          temp=stk.top();
          stk.pop();
          if(temp!='{')
              return False;
          break;
      }
      case ']':
      {
          temp=stk.top();
          stk.pop();
          if(temp!='[')
              return False;
          break;
      }
      default: return False;

  }//switch
  }//for
return(stk.empty()); //return true if stack becomes empty after going through all                        //iterations
}//fun


int main()
{
  string str;
  cout<<"enter the string to be checeked"<<endl;
  cin>>str;
  if(IsBalanced(str)
      cout<<"string "<<str<<" is balanced"<<endl;
  else
      cout<<"string "<<str<<" is not balanced"<<endl;
}

Questions