4. Stack And Its Applications

Objective: Discuss the stack data structure, and its applications in computer programming.

In this lecture unit, we show:

how to implement the stack class,
how to use a stack to check for balanced symbols,
how to use operator precedence parsing to evaluate infix expressions.

4.1 Stack Data Structure

A (pushdown) stack is a linear list of objects into which new objects can be inserted and from which objects can be removed. The insertion and deletion of objects are done to the same end, called the top of the stack.
The stack is a LIFO (Last-In-First-Out) data structure.

4.2 Array-Based Implementation (1)

// Array based Stack

template <class T>
class Stack
{
public:
  Stack() : theArray(1)
    { topOfStack = -1; }

  bool isEmpty() const
    { return topOfStack == -1; }
  const T& top() const;

  void makeEmpty()
    { topOfStack = -1; }
  T pop();
  void push(const T& x);

private:
  vector<T> theArray;
  int topOfStack;
};

4.3 Array-Based Implementation (2)

#include "Stack.h"

template <class T>
void Stack<class T>::push(const T& x)
{
  if (topOfStack == theArray.size() - 1)
    theArray.resize(theArray.size() * 2 + 1);
  theArray[++topOfStack] = x;
}

template <class T>
const T& Stack<class T>::top() const
{
  if (isEmpty())
    throw UnderflowException();
  return theArray[topOfStack];
}

template <class T>
T Stack<class T>::pop()
{
  if (isEmpty())
    throw UnderflowException();
  return theArray[topOfStack--];
}

4.4 Linked-List-Based Stack (1)

template <class T>
class Stack
{
public:
  Stack() : topOfStack(NULL) {}
  Stack(const Stack& rhs);
  ~Stack() { makeEmpty(); }

  bool isEmpty() const
    { return topOfStack == NULL; }
  const T& top() const;
  void makeEmpty();
  T pop();
  void push(const T& x)
    { topOfStack = new ListNode(x, topOfStack); }
  const Stack& operator=(const Stack& rhs);

private:
  struct ListNode
  {
    T element;
    ListNode *next;

    ListNode(const T& theElement, ListNode *n = NULL)
      : element(theElment), next(n) {}
  };
  ListNode *topOfStack;
};

4.5 Linked-List-Based Stack (2)

template <class T>
const Stack<T> &
Stack<class T>::operator=(const Stack<class T>& rhs)
{
  if (this != &rhs)
  {
    makeEmpty();
    if (rhs.isEmpty())
      return *this;

    ListNode *rp = rhs.topOfStack;
    ListNode *p = new ListNode(rp->element);
    topOfStack = p;

    for (rp = rp->next; rp != NULL; rp = rp->next)
      p = p->next = new ListNode(rp->element);
  }
  return *this;
}

template <class T>
Stack<class T>::Stack(const Stack<class T>& rhs)
{
  topOfStack = NULL
  *this = rhs;
}

template <class T>
T Stack<class T>::pop()
{
  if (isEmpty())
    throw UnderflowException();
  ListNode *oldTop = topOfStack;
  T elt = oldTop->element;
  topOfStack = topOfStack->next;
  delete oldTop;
  return elt;
}


template <class T>
const T& Stack<class T>::top() const
{
  if (isEmpty())
    throw UnderflowException();
  return topOfStack->element;
}

template <class T>
void Stack<class T>::makeEmpty()
{
  while (!isEmpty())
    pop();
}

4.6 Prefix, Infix, and Postfix Notations

Let @ be any dyadic (binary) operator, and A and B be the two operands. There are three ways to write the operation:

  A @ B (infix)
  @ A B (prefix)
  A B @ (postfix)

Examples:

  Infix               Prefix            Postfix
  A+B                 +AB               AB+
  A+B-C               -+ABC             AB+C-
  (A+B)*(C-D)         *+AB-CD           AB+CD-*
  A^B*C-D+E/F/(G+H)   +-*^ABCD//EF+GH   AB^C*D-EF/GH+/+

4.7 Conversion From Infix

Convert the operations one at a time in the order in which they are performed. Then remove all parentheses.

Examples:

  (A + B) * (C - D)
= (+ A B) * (- C D)
= * (+ A B) (- C D)
= * + A B - C D

  (A + B) * (C - D)
= (A B +) * (C D -)
= (A B +) (C D -) *
= A B + C D - *

The rule of conversion can be restated as:

Fully parenthsize the expression.
Move all operators so that they replace the corresponding left (right) parenthesis for prefix (postfix) notation.
Remove all parentheses.

Example:

  A / B ^ C + D * E - A * C
= (((A / (B ^ C)) + (D * E)) - (A * C))

Hence,

 Prefix  : - + / A ^ B C * D E * A C
 Postfix : A B C ^ / D E * + A C * -.

Note:

No parentheses are needed in prefix and postfix notations.
The order of operands are the same in all three notations.
Infix notation is good for people while prefix and postfix notations are good for machines.

4.8 Evaluate Postfix Expressions

real evaluatePostfix(E)
{
   Stack S;
   while (E is not empty)
   {
      x = delete_next_token(E);
      if (x is an operand)
         S. push (x);
      else if (x is an operator)
      {
         b = S.pop();
         a = S.pop();
         c = applying x to a and b;
         S.push(c);
      }
      else
         exit( invalid);
   }

   value = S.pop();
   if (S.IsEmpty())
      return(value);
   else
      exit(invalid);
}

Example: Consider the postfix expression

         6 2 3 + - 3 8 2 / + * 2 ^ 3 +

The execution of evaluatePostfix is depicted by the following snapshots of the stack.

 Next Token  Stack
 ==========  ================================
 None        Empty
 6           6
 2           6, 2
 3           6, 2, 3
 +           6, 5
 -           1
 3           1, 3
 8           1, 3, 8
 2           1, 3, 8, 2
 /           1, 3, 4
 +           1, 7
 *           7
 2           7, 2
 ^           49
 3           49, 3
 +           52

4.9 Conversion From Infix (2)

infixToPostfix(E)
{
   Stack S('(');
   append `)' to E;
   rank = 0;
   x = delete_next_token(E);

   do
   {
      if (S.isEmpty())
         exit ( invalid);

      while (isp(S.top()) > icp(x))
      {
         output y = S.pop());
         rank = rank + r(y);
         if (rank < 1)
            exit (invalid);
      }

      if (isp(S.top()) = icp(x))
         S.pop();
      else
         S.push(x);

      x = delete_next_token(E);
   } while (E is not empty);

   if ( not S.isEmpty() or rank != 1)
      exit(invalid);
}

The icp(x) (in-coming priority), isp(x) (in-stack priority), and r(x) (rank) of symbol x are defined as follows:

 Symbol x   icp(x)   isp(x)   r(x)
 ========   ======   ======   ====
 + -        1        2        -1
 * /        3        4        -1
 ^          6        5        -1
 Operand    7        8         1
 (          9        0        --
 )          0        -        --

Example: A * (B + C) * D ^ E ^ F

 Next Token  Stack   Output So Far  Rank
 ==========  ======  =============  ====
             (                      0
 A           (A                     0
 *           (*      A              1
 (           (*(     A              1
 B           (*(B    A              1
 +           (*(+    AB             2
 C           (*(+C   AB             2
 )           (*(+    ABC            3
             (*(     ABC+           2
             (*      ABC+           2
 *           (*      ABC+*          1
 D           (*D     ABC+*          1
 ^           (*^     ABC+*D         2
 E           (*^E    ABC+*D         2
 ^           (*^^    ABC+*DE        3
 F           (*^^F   ABC+*DE        3
 )           (*^^    ABC+*DEF       4
             (*^     ABC+*DEF^      3
             (*      ABC+*DEF^^     2
             (       ABC+*DEF^^*    1
                     ABC+*DEF^^*    1