CIS 121 April 5, 2000

There are three announcements today.

Recall that Advising has begun. Freshmen and Sophomores must sign up at http://www.cis.usouthal.edu/advising. Juniors, Seniors, and Graduate Students must sign up on the board in FCW 20. Time is running short. Advising for Juniors, Seniors, and Graduate students will only last for two weeks. After that time, even if you meet with an advisor, there will still be a block placed on your registration. So make sure you sign up soon. Advising for Freshmen and Sophomores will last for three weeks. Each Freshmen and Sophomore is assigned a particular week to be advised. You will be told what week you have been assigned when you sign up.
There are three scholarships and one fellowship available to deserving students. You can find applications in the main School of CIS office, FCW 20, or you can apply online at http://www.cis.usouthal.edu/scholarships/2000ScholarshipFellowship.html. The deadline has been extended until next Monday, April 10, 2000.
The Annual ACM Banquet will be held this year on the Battleship Alabama on April 22. The winners of the scholarships and fellowships will be announced at the banquet. The cost of the banquet until this Friday is $22.50. After Friday the cost will be $25. The banquet will consist of a nice dinner and dancing after dinner on the Battleship. All students are encouraged to attend. If you need more information, you may contact the ACM Faculty sponsor, Dr. David Langan.

Stacks

We will continue our discussion of stacks. Recall that we look at several methods naturally associated with stacks.

push - place an element on to the stack.

pop - take an element off the top of the stack.

peek - examine the element on the top of the stack without taking it.

empty - determine whether or not the stack is empty.

search - search for the position of a particular element of the stack.

There is a predefined class called Stack in the java.util package that implements these methods for us. The interface of that class is

public class Stack extends Vector {
   public Stack();

   public boolean empty();
   public Object peek();
   public Object pop();
   public Object push(Object item);
   public int search(Object o);
}

The example that we have looked at to illustrate the use of stacks is converting arithmetic expressions from infix notation to postfix or Reverse Polish Notation.

An arithmetic expression is classified as infix if the arithmetic operator is placed between the operands on which it is to operate. Notice that this requires the use of parentheses in some cases.

In writing compilers it is more convenient to evaluate an arithmetic expression if it is written in Reverse Polish Notation.

We have looked at the simple example of converting the infix expression a+b into the Reverse Polish Notation ab+. Let us look again at the algorithm used.

Recall that we surround the expression with brackets. We place the following priorities on valid arithmetic operators.

Operator	Priority
[	0
{	1
-	2
+	2
/	3
*	3
^	4

To convert infix notation to Reverse Polish Notation we use the following algorithm found on page 529 of your book.

for every character in the infix expression
      if next character is closing parenthesis ')'
         pop operator from stack
         while operator not opening parenthesis '('
            store operator in string buffer
            pop operator from stack
      else if next character is closing bracket ']'
         pop operator from stack
         while operator not opening bracket '['
            store operator in string buffer
            pop operator from stack
      else if next character is opening parenthesis '(' or opening bracket '['
         push next character on to stack
      else if next character is arithmetic operator
         while priority of next character is <= priority of stack top operator
            pop operator from stack
            store operator in string buffer
         push next character on to stack
      else
         store next character in string buffer

Let us look at this algorithm in action.

Reverse Polish Notation

Now let us look at how this algorithm may be implemented.

import java.util.*;

public class ReversePolishNotation {
   String inputString;
   String outputString = "";

   public ReversePolishNotation(String s) {
      inputString = s;
   }

   private int priority(String s) {
      int operatorPriority = -1;

      if (s.equals("["))
         operatorPriority = 0;
      else if (s.equals("("))
         operatorPriority = 1;
      else if (s.equals("+"))
         operatorPriority = 2;
      else if (s.equals("-"))
         operatorPriority = 2;
      else if (s.equals("*"))
         operatorPriority = 3;
      else if (s.equals("/"))
         operatorPriority = 3;
      else if (s.equals("^"))
         operatorPriority = 4;

      return(operatorPriority);
   }

   private void convert() {
      Stack myStack = new Stack();
      String nextCharacter;
      String topOfStack;

      for (int i = 0;i<=inputString.length()-1;i++) {
         nextCharacter = inputString.substring(i,i+1);
         System.out.println(nextCharacter);
         if (nextCharacter.equals(")")) {
            topOfStack = (String)myStack.pop();
            while (!topOfStack.equals("(")) {
               outputString += topOfStack;
               topOfStack = (String)myStack.pop();
            }
         } else if (nextCharacter.equals("]")) {
            topOfStack = (String)myStack.pop();
            while (!topOfStack.equals("[")) {
               outputString += topOfStack;
               topOfStack = (String)myStack.pop();
            }
         } else if (nextCharacter.equals("(") ||
                    nextCharacter.equals("[")) {
            myStack.push(nextCharacter);
         } else if (nextCharacter.equals("+") ||
                    nextCharacter.equals("-") ||
                    nextCharacter.equals("*") ||
                    nextCharacter.equals("/") ||
                    nextCharacter.equals("^")) {
            topOfStack = (String)myStack.peek();
            while (priority(nextCharacter) <= priority(topOfStack)) {
               topOfStack = (String)myStack.pop();
               outputString += topOfStack;
               topOfStack = (String)myStack.peek();
            }
            myStack.push(nextCharacter);
         } else {
            outputString += nextCharacter;
         }             
      }
   }

   public String toString() {
      return(outputString);
   }

   public static void main(String[] args) {
      ReversePolishNotation myConverter = new ReversePolishNotation("[a+b]");
      myConverter.convert();
      System.out.println(myConverter);
   }
}

You may download this source code.

Source Code.

Notice how abstraction has come into play. We have worked with a Stack and seen its methods work without any consideration of how those methods are implemented. But now let's look at some implementation issues.

Recall that the Stack class extends the Vector class.

As we have seen before a simple example of a data structure is an array. An array can hold primitive data types and object references. A limitation of an array is that we have to specify how large it is. We can access the size of an array by the length variable associated with arrays. However, we cannot change the size of the array. When new elements are added to an array we must write the code to move other elements if we need to.

The Vector class provides us with an easier way to approach this problem. Unlike an array, a Vector can only hold object references. Therefore if we wish to place a primitive data type into a Vector we have to place it in a wrapper class. Another advantage of a Vector is that a Vector can grow dynamically. We can keep adding elements to a Vector and it will expand to hold those object references. We can control both the initial capacity and the growth factor of the Vector. There are three constructors for the Vector class.

Vector() - creates an empty vector with initial capacity 10.

Vector(int cap) - creates an empty vector with initial capacity cap.

Vector(int cap,int grow) - creates an empty vector with initial capacity
                           cap and growth factor grow.

There are also several methods available in the Vector class. Some of the methods are:

boolean isEmpty() - determines whether or not the Vector is empty
int size() - returns the number of elements in the Vector
void addElement(Object) - adds Object to the end of the Vector
void insertElementAt(Object,int) - adds an element at the given location
Object firstElement() - returns the first element in the Vector
void removeAllElements() - empties the Vector
Object lastElement() - returns the last element in the Vector
int indexOf(Object) - returns the position of the Object in the Vector
int indexOf(Object,int) - returns the position of the first location of Object starting at the position int
Object elementAt(int) - returns the object at position int
boolean contains(Object) - determines whether or not the Object is in the Vector
boolean removeElement(Object) - removes Object from the Vector if it is found
void removeElementAt(int) - removes the Object at position int

Notice one important thing about a Vector. Unlike arrays, every element in a Vector is an Object. Recall that the class structure in Java is hierarchical and every class inherits from the Object class. So every object in Java is of type Object. So we must keep track of what type of Object is placed in the Vector because we will have to cast it back to its original type after we retrieve it from the Vector.

Since Vectors can give us most of the same functionality of an array and can grow dynamically, one might wonder why we don't just abandon arrays and use Vectors. One reason for that is that not every language supports Vectors, whereas almost every language supports arrays.

As a comparison, let us consider today how we would implement the methods of a stack using arrays instead of Vectors. One obvious limitation we have is that we will have to specify the maximum size of the Stack.

public class Stack {






}