Description
Objectives
Further understanding of interfaces
Introduction to the applications of stacks
Introduction to the implementation of stacks
Introduction
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: Stack.java.
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: ArrayStack.java.
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
ITI 1221. Introduction to Computer Science II Summer 2015 2015-06-28, 12:15
http://www.site.uottawa.ca/~lucia/courses/ITI1121-15/assignments/a2/index.html Page 2 of 7
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.
add:
pops off the top two elements from the operands stack, adds them together and pushes back the result
onto the stack;
sub:
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”;
exch:
exchanges the order of the two elements on the top of the stack.
dup:
duplicates the top element of the stack;
pstack:
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,
-topINTEGER: 3
-bottom-
-topINTEGER: 3
INTEGER: 3
-bottom-
-topINTEGER: 6
-bottomThe 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();
ITI 1221. Introduction to Computer Science II Summer 2015 2015-06-28, 12:15
http://www.site.uottawa.ca/~lucia/courses/ITI1121-15/assignments/a2/index.html Page 3 of 7
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.
Token:
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;
}
ITI 1221. Introduction to Computer Science II Summer 2015 2015-06-28, 12:15
http://www.site.uottawa.ca/~lucia/courses/ITI1121-15/assignments/a2/index.html Page 4 of 7
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”;
}
}
}
Reader:
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 );
ITI 1221. Introduction to Computer Science II Summer 2015 2015-06-28, 12:15
http://www.site.uottawa.ca/~lucia/courses/ITI1121-15/assignments/a2/index.html Page 5 of 7
try {
return new Token( Integer.parseInt( t ) );
} catch ( NumberFormatException e ) {
return new Token( t );
}
}
}
Run:
contains the main method.
public class Run {
public static void main( String[] args ) {
Calculator c = new Calculator();
for ( int i=0; i
