CS231 lecture notes, Fall 1998
Week 8, Monday 

Quiz Wednesday on the homework preparation.

1) Implementation of stacks

   a) using arrays
   b) using lists (this time the lists are implemented internally)


Most of this is almost identical to the array implementation
of PriorityQueue:

public class Stack {
  private int count;
  private int capacity;
  private int capacityIncrement;
  private Object[] itemArray;

  public Stack () {
    count = 0;
    capacity = 10;
    capacityIncrement = 10;
    itemArray = new Object[capacity];
  }

  public boolean empty () {
    return (count == 0);
  }

  public void push (Object obj) {
    if (count == capacity) {
      capacity += capacityIncrement;
      capacityIncrement *= 2;
      Object[] tempArray = new Object[capacity];
      for (int i=0; i<count;i++) {
        tempArray[i] = itemArray[i];
      }
      itemArray = tempArray;
    }
    itemArray[count] = obj;
    count++;
  }

The first difference is that we are dealing with Objects instead
of PQItems, but other than that the only interesting difference is
in pop:

  public Object pop () {
    if (count == 0) return null;
    count--;
    return itemArray[count];
  }

We can just pull the top item off the stack -- no need to search
for the one with the highest key.  Based on pop, peek is a no-
brainer:

  public Object peek () {
    if (count == 0) return null;
    return itemArray[count-1];
  }

For the list implementation, we need a new kind of list node that
has an Object as cargo:

public class StackNode {
  Object item;
  StackNode next;

  StackNode (Object item_, StackNode next_) {
    item = item_;
    next = next_;
  }
}

The instance variable here is called topNode and it just
point to the element on the top of the stack:

public class Stack {
  StackNode topNode;

  public Stack () {
    topNode = null;
  }

The constructor creates an empty stack by initializing the
instance varaible to null.  So naturally we can test for an
empty stack as so...

  public boolean empty () {
    return (topNode == null);
  }

Now, for putting things on and taking things off the list,
we could have used the list methods we developed at the beginning
of the semester, but it turns out that the list operations we
want to perform are so simple that we can pretty much go ahead
and do them ourselves.

push is the same as addNewFirstNode:

  public void push (Object obj) {
    topNode = new StackNode (obj, topNode);
  }

pop is the same as removeFirstNode, except that we have to play
some games with a temporary variable:

  public Object pop () {
    if (topNode == null) return null;
    Object ret = topNode.item;
    topNode = topNode.next;
    return ret;
  }

peek is a no-brainer.

  public Object peek () {
    if (topNode == null) return null;
    return topNode.item;
  }



PART TWO
--------

Stack based evaluation of postfix expressions.

Basic rules for interpreting postfix:

1) see an operand, push it on the stack

2) see an operator, pop to things off the stack and apply
   the operator to them.  Push the result off the stack

Tricky things:

       1) keeping track of what order to apply the operation
          when you get the two things off the stack
       2) dealing with stack empty errors and such

Examples:

34+    means... push 3 push 4 pop pop add
342*+  means 4*2+3

What does

31- mean?  3-1 or 1-3?

It's 3-1, which implies that when we pop things off the stack,
we pop the SECOND ARGUMENT FIRST!


What are the tools we are going to need to code this up?

1) ability to traverse a string and extract characters and
   (maybe) ranges.
2) ability to identify digits and operators
3) ability to put integers onto a Stack

For each of these things, you should look up the relevant
documentation and test out some simple cases in isolation
until you know what you are doing.

Development plan?