A generic type is a type that is specified at run time rather than at compile time. A generic type uses formal type parameters, which are expressions written within angle brackts, e.g., <K, V>.
In this lab we will use a generic stack in the implementation of a postfix calculator, which is a calculator that processes postfix arithmetic expressions.
The generic Stack interface is defined as follows, where the symbol <E> is the stack's type parameter:
public interface Stack<E> {
public int size();
public boolean isEmpty();
public E top() throws EmptyStackException;
public void push (E element);
public E pop() throws EmptyStackException;
}
Note that the push() and pop() methods use the generic parameter E
as their type. In our previous definition of the Stack interface, E was replaced
by Object.
In addition to enforcing type safety, one of the main advantages of the generic types is they reduce the need for casting operations. To illustrate this, consider the following use of a generic stack:
Object o = null;
ArrayStack<Integer> A = new ArrayStack<Integer>(); // An Integer stack
A.push(7); // 7 is boxed into an Integer
System.out.println(A.pop() + 5); // Outputs 12 -- no cast needed
A.push(9);
System.out.println(A.pop() + 10); // Outputs 19 -- no cast needed
ArrayStack<String> B = new ArrayStack<String>(); // A String stack
B.push("Bob");
B.push("Alice");
System.out.println(B.pop()); // Prints Alice
B.push("Eve");
System.out.println(B.pop()); // Prints Eve
For each token in the postfix expression
if the token is a number
push it on the stack
else // the token is the operator, op
op2 = pop the stack
op1 = pop the stack
push op1 op op2
Return pop()
As this algorithm describes, when given a postfix expression you first
break the expression into its tokens, then for each token, if it is
a number, you push it on the stack, if it is an operator, you pop
the top two stack elements and apply that operator to them. Here's
an example of how this would be implemented in Java:
public int evaluate(String s) {
Stack<Integer> stack = new ArrayStack<Integer>();
StringTokenizer st = new StringTokenizer(s);
while (st.hasMoreTokens()) {
String element = st.nextToken();
if (isNumber(element)) {
stack.push(new Integer((Integer.parseInt(element))));
}
else {
ExpressionOperator op;
Integer opnd2 = null, opnd1 = null;
switch (element.charAt(0)) { // Must be an operator
case '+':
op = new AdditionOperator();
opnd2 = stack.pop();
opnd1 = stack.pop();
op.setOperands(opnd1, opnd2);
stack.push(op.getValue());
break;
}
}
}
return stack.pop();
}
Note that this implemention uses a generic stack that is instantiated
to an Integer. Note also that it uses an AdditionOperator
object to carry out the operation:
public class AdditionOperator extends ExpressionOperator {
public Integer getValue() {
return (firstOperand + secondOperand); // unboxing and then autoboxing
}
public String toString() { return new String("+");
}
}
This will create a subdirectory named net/datastructures in your current directory. This is where the .class files are stored for those classes contained in the net.datastructures package. Given this setup, here is how you will compile and run your program:jar xvf postfix.jar -- This will extract the archive and create the /net/datastructures directories
javac -d . PostFixCalculator.java -- This will compile everything, adding to net java net.datastructures.PostFixCalculator -- This will run your calculator
The -d . tells javac to store the class files in the current directory and will force it to locate them in net.datastructures.