This assignment is about three implementations of the interface Stack as well as an application of a Stack.
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.
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.
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.
The execution of the following PostScript program,
> java Run "3 pstack dup pstack add pstack"
|
produces the following output,
-top-
INTEGER: 3 -bottom- -top- INTEGER: 3 INTEGER: 3 -bottom- -top- INTEGER: 6 -bottom- |
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.
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"; } } } |
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 ); } } } |
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.
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 ArrayStack.java to a new file called DynamicArrayStack.java. 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).
In Java you can’t actually increase the size of an array, so what you have to do is allocate a new array which is bigger than the existing one, copy all the elements from the old array into the new one, set the instance variable to point at the new array, and then proceed adding the element.
Several strategies are possible to increase the size of the array. Here, you will be implementing the following one. The initial size of the stack is determined by the parameter of the constructor of the class DynamicArrayStack( int capacity ). Every time the array will be full, the method push will create an array that has 1.5 times its current capacity.
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 ).
Token t = r.nextToken();
operands.push( t ); |
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).
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: