CSCI 146: Lab 10 Materials

The main goal of Lab 10 is to enhance the students' understanding of stack operations by implementing a program to convert fully parenthesized infix ("algebraic") expressions to postfix ("RPN") expressions.

• Pseudocode for this problem is given on p.314 of your textbook (Figure 6.9).
• You do not need to read in an expression: you are allowed to hardcode in the infix expression to be converted.
• You need to write a driver program to do the conversion.
• You must follow the pseudode.
• Use the stack (ObjectStack class) implementation linked here, which contains a method called toString (written by Mr. Bing Xia) that is useful to display the contents of the stack.
  
  

  
  import java.util.EmptyStackException;
  
  public class ObjectStack implements Cloneable
  {
     private Object[ ] data;
     private int manyItems; 
  
     public ObjectStack( )
     {
        final int INITIAL_CAPACITY = 10;
        manyItems = 0;
        data = new Object[INITIAL_CAPACITY];
     }
  
     public ObjectStack(int initialCapacity)
     {
        if (initialCapacity < 0)
           throw new IllegalArgumentException
           ("initialCapacity too small " + initialCapacity);
        manyItems = 0;
        data = new Object[initialCapacity];
     }
  
     public Object clone( )       
     {  // Clone an ObjectStack.
        ObjectStack answer;
        
        try
        {
           answer = (ObjectStack) super.clone( );
        }
        catch (CloneNotSupportedException e)
        { 
           throw new RuntimeException
           ("This class does not implement Cloneable");
       }
        
        answer.data = (Object [ ]) data.clone( );
        
        return answer;
     }        
  
     public void ensureCapacity(int minimumCapacity)
     {
        Object biggerArray[ ];
        
        if (data.length < minimumCapacity)
        {
           biggerArray = new Object[minimumCapacity];
           System.arraycopy(data, 0, biggerArray, 0, manyItems);
           data = biggerArray;
        }
     }
  
     public int getCapacity( )   
     {
        return data.length;
     }
  
     public boolean isEmpty( )
     {
        return (manyItems == 0);
     }
     
     public Object peek( )   
     {
        if (manyItems == 0)
           throw new EmptyStackException( );
        return data[manyItems-1];
     }
  
     public Object pop( )
     {
        if (manyItems == 0)
           throw new EmptyStackException( );
        return data[--manyItems];
     }
  
     public void push(Object item)
     {
        if (manyItems == data.length)
        {
           ensureCapacity(manyItems*2 + 1);
        }
        data[manyItems] = item;
        manyItems++;
     }
                
     public int size( )   
     {
        return manyItems;
     }
  
  
     public void trimToSize( )
     {
        Object trimmedArray[ ];
        
        if (data.length != manyItems)
        {
           trimmedArray = new Object[manyItems];
           System.arraycopy(data, 0, trimmedArray, 0, manyItems);
           data = trimmedArray;
        }
     } 
  
     public String toString()
      {
  	StringBuffer buf = new StringBuffer();
  
  	for(int i = 0; i < manyItems; i++) {
  	    buf.append("[" + data[i] + "]  ");
  	}
  	return buf.toString();
      }
  }