ITI 1221. Introduction to Computer Science II Summer 2015

Assignment 2

Deadline: Monday July 6, 23:59 (strongly suggested to hand-in by July 3rd)



This assignment is about three implementations of the interface Stack as well as an application of a Stack.

1 Modifying the interface Stack: adding a method clear() [5 marks]

Modify the interface Stack below adding an abstract method public void clear().
public interface Stack {  
    public abstract boolean isEmpty();  
    public abstract Object peek();  
    public abstract Object pop();  
    public abstract void push( Object element );  

Click here:

2 Implementing the method clear() in the class ArrayStack [5 marks]

The class ArrayStack uses a fixed size array and implements the interface Stack. Now that the interface Stack has been modified to have a method clear(), the current implementation of the class ArrayStack is broken (try compiling it without making any change).

Since the class ArrayStack implements the interface Stack, it has to provide an implementation for all the methods that are declared by the interface. Consequently, write an implementation for the method void clear(). It removes all of the elements from this ArrayStack. The stack will be empty after this call returns.

Click here:

3 Using a stack: Calculator [30 marks]

In this question, there is a simple stack-based language to evaluate arithmetic expressions. The language for this question is actually a sub-set of a language called PostScript, which is a file format often used with printers. The main data-structure used by a PostScript interpreter is a stack. For the interpreter presented in the next pages, you must implement the operations add, sub, exch, dup, and pstack. Here are the 5 instructions of the language.

pops off the top two elements from the operands stack, adds them together and pushes back the result onto the stack;
pops off the top two elements from the operands stack, subtracts them together and pushes back the result onto the stack. E.g.: (3 - 1) would be represented as “3 1 sub”;
exchanges the order of the two elements on the top of the stack.
duplicates the top element of the stack;
prints the content of the stack. It is important that the content of the stack remains the same after a call to the instruction pstack. The operation must not destroy or modify the content of the stack. Use the format of the example below.

The execution of the following PostScript program,
> java Run "3 pstack dup pstack add pstack"

produces the following output,

The class Calculator is an interpreter for the language. The implementation requires three additional classes: an implementation of a Stack, Token and Reader.
public class Calculator {  
    private Stack operands;  
    public Calculator() {  
        operands = new ArrayStack( 100 );  
    public void execute( String program ) {  
        Reader r = new Reader( program );  
        while ( r.hasMoreTokens() ) {  
            Token t = r.nextToken();  
            if ( ! t.isSymbol() ) {  
                operands.push( t );  
            } else if ( t.sValue().equals("add") ) {  
                // the implementation of the operation ‘‘add’’  
            } else if ( t.sValue().equals("sub") ) {  
                // the implementation of the operation ‘‘sub’’  
            } else if ( t.sValue().equals("exch") ) {  
                // the implementation of the operation ‘‘exch’’  
            } else if ( t.sValue().equals("dup") ) {  
                // the implementation of the operation ‘‘dup’’  
            } else if ( t.sValue().equals("pstack") ) {  
                // the implementation of the operation ‘‘pstack’’  

The input for the method execute is a string that contains a valid PostScript program, e.g. “1 pstack dup pstack”. The input is parsed into tokens by the Reader. For the current example, the first call to the method nextToken() returns a token that represents the 1, the second call returns a token that represents the symbol pstack, and so on. The tokens that are not symbols are pushed onto the stack whilst the symbols are immediately evaluated. Here is a brief description of the classes Token and Reader.

A token is an immutable object that represents either a boolean value, an integer or a symbol.
class Token {  
    private static final int BOOLEAN = 0;  
    private static final int INTEGER = 1;  
    private static final int SYMBOL = 2;  
    private boolean bValue;  
    private int iValue;  
    private String sValue;  
    private int type;  
    Token( boolean bValue ) {  
        this.bValue = bValue;  
        type = BOOLEAN;  
    Token( int iValue) {  
        this.iValue = iValue;  
        type = INTEGER;  
    Token( String sValue ) {  
        this.sValue = sValue;  
        type = SYMBOL;  
    public boolean bValue() {  
        if ( type != BOOLEAN )  
            throw new IllegalStateException( "not a boolean" );  
        return bValue;  
    public int iValue() {  
        if ( type != INTEGER )  
            throw new IllegalStateException( "not an integer" );  
        return iValue;  
    public String sValue() {  
        if ( type != SYMBOL )  
            throw new IllegalStateException( "not a symbol" );  
        return sValue;  
    public boolean isBoolean() { return type == BOOLEAN;  }  
    public boolean isInteger() { return type == INTEGER;  }  
    public boolean isSymbol()  { return type == SYMBOL;   }  
    public String toString() {  
        switch (type) {  
        case BOOLEAN: return "BOOLEAN: " + bValue;  
        case INTEGER: return "INTEGER: " + iValue;  
        case SYMBOL:  return "SYMBOL: "  + sValue;  
        default:      return "INVALID";  

A reader parses the input string into Tokens.
class Reader {  
    private StringTokenizer st;  
    Reader( String s ) {  
        st = new StringTokenizer(s);  
    public boolean hasMoreTokens() {  
        return st.hasMoreTokens();  
    public Token nextToken() {  
        String t = st.nextToken();  
        if ( "true".equals( t ) )  
            return new Token( true );  
        if ( "false".equals( t ) )  
            return new Token( false );  
        try {  
            return new Token( Integer.parseInt( t ) );  
        } catch ( NumberFormatException e ) {  
            return new Token( t );  

contains the main method.
public class Run {  
    public static void main( String[] args ) {  
        Calculator c = new Calculator();  
        for ( int i=0; i<args.length; i++ ) {  
            c.execute( args[ i ] );  

For this question, you must complete the implementation of the 5 instructions (add, sub, exch, dup and pstack) in the class Calculator.

4 Implement the class DynamicArrayStack (by modifying ArrayStack) [25 marks]

The class ArrayStack has a severe limitation, its capacity is fixed. In class, we have seen an implementation technique called “dynamic array” that allows to circumvent this limitation.

Create a new class called DynamicArrayStack. For this, you will use the class ArrayStack as a starting point. Simply copy the file to a new file called Make all the necessary changes so that it can be compiled. In particular, change the name of the class to DynamicArrayStack and change the name of the constructor accordingly. Make sure that you have a valid starting point (i.e. this new class can be compiled).

5 Creating a LinkedStack [30 marks]

In class, we have seen a new technique for implementing data structures that has the following benefits:

Create an implementation for the interface Stack using linked elements (the lecture notes contain most of the implementation details). Besides implementing the methods of the interface Stack, the LinkedStack must implement the instance method booleean equals( Object o ).

6 Rules and Regulations [5 marks]

  • Please follow the general directives for assignments.
  • You must abide by the following submission instructions:
    Include all your java files into a director called u1234567 where 1234567 is your student id.
    Zip this directory and submit via blackboard.
    The directory must contain the following files (with your implementation):

  • The assignment is individual (plagiarism or collaborations towards the solution of the assignment will not be tolerated).
    Read the information on academic fraud below.
  • NOTES:

    1. Note on implementing the operations "add" and "sub" for the Calculator.
      Every time the stack will contain only objects of type Token; as you can see in part of the startup code given:
      Token t = r.nextToken();  
      operands.push( t );
      So, every time you pop() you know you will be getting back an object of class Token and that it should represent an integer. You need to look inside class Token for methods useful to retrieve the value of this integer.

      Hint: at all times, the stack should only contain Tokens, this will simplify the implementation (this implies that the objects added onto the stack will be Tokens).

    2. For the method equals of the class LinkedStack, it would seem to need special cases for situations where other designates an ArrayStack, a LinkedStack or an ArrayStack. This is not the case!
      Read the question carefully, other may designate any valid implementation of a Stack (including UnknownStack, as long as UnknownStack is a valid implementation of the interface Stack). You cannot assume a particular implementation.

    Academic fraud

    This part of the assignment is meant to raise awareness concerning plagiarism and academic fraud. Please read the following documents.

    Cases of plagiarism will be dealt with according to the university regulations.

    By submitting this assignment, you acknowledge:

    1. having read the academic regulations regarding academic fraud, and
    2. understanding the consequences of plagiarism