September 15th, 2015

Classwork
A Stack Collection
Let’s look at a different example of a collection. A stack is a linear collection whose elements are added and removed from the same end. We say that a stack is processed in a last in, first out (LIFO) manner. That is, the last element to be put on a stack will be the first one that gets removed. Said another way, the elements of a stack are removed in the reverse order of their placement on it. In fact, one of the principal uses of a stack in computing is to reverse the order of something (e.g., an undo operation). The processing of a stack is shown in Figure 3.3. Usually a stack is depicted vertically, and we refer to the end to which elements are added and from which they are removed as the top of the stack.

Recall from our earlier discussions that we define an abstract data type (ADT) by identifying a specific set of operations that establishes the valid ways in which we can manage the elements stored in the data structure. We always want to use this concept to formally define the operations for a collection and work within the functionality it provides. That way, we can cleanly separate the interface to the collection from any particular implementation technique used to create it.

The operations for a stack ADT are listed in Figure 3.4. In stack terminology, we push an element onto a stack and we pop an element off a stack. We can also peek at the top element of a stack, examining it or using it as needed, without ac- tually removing it from the collection. There are also the general operations that allow us to determine if the stack is empty and, if not empty, how many elements it contains.

Sometimes there are variations on the naming conventions for the operations on a collection. For a stack, the use of the terms push and pop is relatively standard. The peek operation is sometimes referred to as top.

push – Adds an element to the top of the stack.
pop – Removes an element from the top of the stack.
peek – Examines the element at the top of the stack.
isEmpty – Determines if the stack is empty.
size – Determines the number of elements on the stack.

A Stack ADT

/**
 *  @author Lewis and Chase
 *
 *  Defines the interface to a stack data structure.
 */
package jss2;
public interface StackADT
{
   /** Adds one element to the top of this stack.
    *  @param element element to be pushed onto stack
    */
   public void push (T element);
   /** Removes and returns the top element from this stack.
    *  @return T element removed from the top of the stack
    */
   public T pop();
   /** Returns without removing the top element of this stack.
    *  @return T element on top of the stack
    */
   public T peek();
   /** Returns true if this stack contains no elements.
    *  @return boolean whether or not this stack is empty
    */
   public boolean isEmpty();
   /** Returns the number of elements in this stack.
    *  @return int number of elements in this stack
    */
   public int size();
   /** Returns a string representation of this stack.
    *  @return String representation of this stack
    */
   public String toString();
}

Using Stacks: Evaluating Postfix Expressions

Let’s look at a slightly more complicated example. Consider the following infix expression:
(3 * 4 – (2 + 5)) * 4 / 2
The equivalent postfix expression is
3 4 * 2 5 + – 4 * 2 /
Applying our evaluation rule results in:
12 2 5 + – 4 * 2 /
then 12 7 – 4 * 2 /
then 5 4 * 2 /
then 20 2 /
then 10

The algorithm for evaluating a postfix expression using a stack can be expressed as follows: Scan the expression from left to right, identifying each token (operator or operand) in turn. If it is an operand, push it onto the stack. If it is an operator, pop the top two elements off of the stack, apply the operation to them, and push the result onto the stack. When we reach the end of the expression, the element remaining on the stack is the result of the expression. If at any point we attempt to pop two elements off of the stack but there are not two elements on the stack, then our postfix expression was not properly formed. Similarly, if we reach the end of the expression and more than one element remains on the stack, then our expression was not well formed.

/**
 * @author Lewis and Chase
 *
 * Demonstrates the use of a stack to evaluate postfix expressions.
 */
import java.util.Scanner;
public class Postfix
{
 /**
  * Reads and evaluates multiple postfix expressions.
  */
 public static void main (String[] args)
 {
   String expression, again;
   int result;
try
{
   Scanner in = new Scanner(System.in);
   do
   {
     PostfixEvaluator evaluator = new PostfixEvaluator();
     System.out.println ("Enter a valid postfix expression: ");
     expression = in.nextLine();
     result = evaluator.evaluate (expression);
     System.out.println();
     System.out.println ("That expression equals " + result);
     System.out.print ("Evaluate another expression [Y/N]? ");
     again = in.nextLine();
     System.out.println();
   }
      while (again.equalsIgnoreCase("y"));
    }
    catch (Exception IOException)
  {
    System.out.println(“Input exception reported");
  } 
 }
}



/**
 * PostfixEvaluator.java
 *
 * Represents an integer evaluator of postfix expressions. Assumes
 * the operands are constants.
 */
import jss2.ArrayStack;
import java.util.StringTokenizer;
public class PostfixEvaluator
{
  /** constant for addition symbol */
  private final char ADD = '+';
  /** constant for subtraction symbol */
  private final char SUBTRACT = '-';
  /** constant for multiplication symbol */
  private final char MULTIPLY = '*';
  /** constant for division symbol */
  private final char DIVIDE = '/';
  /** the stack */
  private ArrayStack stack;

  /**
   * Sets up this evaluator by creating a new stack.
   */
  public PostfixEvaluator()
  {
   stack = new ArrayStack();
  }

  /**
   * Evaluates the specified postfix expression. If an operand is
   * encountered, it is pushed onto the stack. If an operator is
   * encountered, two operands are popped, the operation is
   * evaluated, and the result is pushed onto the stack.
   * @param expr String representation of a postfix expression
   * @return int value of the given expression
   */
  public int evaluate (String expr)
  {
    int op1, op2, result = 0;
    String token;
    StringTokenizer tokenizer = new StringTokenizer (expr);
    while (tokenizer.hasMoreTokens())
    {
      token = tokenizer.nextToken();
    if (isOperator(token))
      {
        op2 = (stack.pop()).intValue();
        op1 = (stack.pop()).intValue();
        result = evalSingleOp (token.charAt(0), op1, op2);
        stack.push (new Integer(result));
       } else
        stack.push (new Integer(Integer.parseInt(token)));
    }
    return result;
  }

  /**
   * Determines if the specified token is an operator.
   * @param token String representing a single token
   * @return boolean true if token is operator
   */
  private boolean isOperator (String token)
  {
    return ( token.equals("+") || token.equals("-") ||
             token.equals("*") || token.equals("/") );
}
  /**
   * Performs integer evaluation on a single expression consisting of
   * the specified operator and operands.
   * @param operation operation to be performed
   * @param op1 the first operand
   * @param op2 the second operand
   * @return int value of the expression
   */
   private int evalSingleOp (char operation, int op1, int op2)
  {
    int result = 0;
    switch (operation)
    {
    case ADD:
      result = op1 + op2;
      break;
    case SUBTRACT:
      result = op1 - op2;
      break;
    case MULTIPLY:
      result = op1 * op2;
      break;
    case DIVIDE:
      result = op1 / op2;
    }
    return result;
   }
 }

Homework:

Implement the ArrayStack Class
Visit edmodo.com to work on a hand trace assignment.