(Java) Provide a complete implementation of class LinkedStack and test it (with

Question

(Java) Provide a complete implementation of class LinkedStack and test it (with a main method) on the PostfixEvaluator applcation (listed below).

package linkedstack;

import java.util.*;

/** Class that can evaluate a postfix expression.
* @author Koffman & Wolfgang
**/
public class PostfixEvaluator {

// Nested Class
/** Class to report a syntax error. */
public static class SyntaxErrorException extends Exception {

/**
* Construct a SyntaxErrorException with the specified
* message.
* @param message The message
*/
SyntaxErrorException(String message) {
super(message);
}
}
// Constant
/** A list of operators. */
private static final String OPERATORS = "+-*/";
// Data Field
/** The operand stack. */
LinkedStack operandStack;

// Methods
/**
* Evaluates the current operation.
* This function pops the two operands off the operand
* stack and applies the operator.
* @param op A character representing the operator
* @return The result of applying the operator
* @throws EmptyStackException if pop is attempted on
* an empty stack
*/
private int evalOp(char op) {
// Pop the two operands off the stack.
int rhs = (int) operandStack.pop();
int lhs = (int) operandStack.pop();
int result = 0;
// Evaluate the operator.
switch (op) {
case '+':
result = lhs + rhs;
break;
case '-':
result = lhs - rhs;
break;
case '/':
result = lhs / rhs;
break;
case '*':
result = lhs * rhs;
break;

}
return result;
}

/**
* Determines whether a character is an operator.
* @param op The character to be tested
* @return true if the character is an operator
*/
private boolean isOperator(char ch) {
return OPERATORS.indexOf(ch) != -1;
}

/**
* Evaluates a postfix expression.
* @param expression The expression to be evaluated
* @return The value of the expression
* @throws SyntaxErrorException if a syntax error is detected
*/
public int eval(String expression) throws SyntaxErrorException {
// Create an empty stack.
operandStack = new LinkedStack();

// Process each token.
// Scanner scan = new Scanner(expression);
try {
String nextToken;
StringTokenizer tokens = new StringTokenizer(expression);
while (tokens.hasMoreTokens()) {               // (nextToken = scan.findInLine("\d+|[-+/\*]")) != null) {
   nextToken = tokens.nextToken();
// Does it start with a digit?
if (Character.isDigit(nextToken.charAt(0))) {
// Get the integer value.
int value = Integer.parseInt(nextToken);
// Push value onto operand stack.
operandStack.push(value);
} // Is it an operator?
else if (isOperator(nextToken.charAt(0))) {
// Evaluate the operator.
int result = evalOp(nextToken.charAt(0));
// Push result onto the operand stack.
operandStack.push(result);
} else {
// Invalid character.
throw new SyntaxErrorException(
"Invalid character encountered");
}
} // End while.

// No more tokens - pop result from operand stack.
int answer = (int) operandStack.pop();
// Operand stack should be empty.
if (operandStack.empty()) {
return answer;
} else {
// Indicate syntax error.
throw new SyntaxErrorException(
"Syntax Error: Stack should be empty");
}
} catch (EmptyStackException ex) {
// Pop was attempted on an empty stack.
throw new SyntaxErrorException(
"Syntax Error: The stack is empty");
}
}
}

Explanation / Answer

import java.util.Iterator;
import java.util.NoSuchElementException;

public class LinkedStack<Item> implements Iterable<Item> {
private int n; // size of the stack
private Node first; // top of stack

// helper linked list class
private class Node {
private Item item;
private Node next;
}

// Initialise an empty stack
public LinkedStack() {
first = null;
n = 0;
assert check();
}

// check if stack is empty
public boolean empty() {
return first == null;
}

// return size of stack
public int size() {
return n;
}

// push an item to stack
public void push(Item item) {
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
n++;
assert check();
}

// pop an item from stack
public Item pop() {
if (empty()) throw new NoSuchElementException("Stack underflow");
Item item = first.item; // save item to return
first = first.next; // delete first node
n--;
assert check();
return item; // return the saved item
}

// get first item
public Item peek() {
if (empty()) throw new NoSuchElementException("Stack underflow");
return first.item;
}

// return a string representation of stack
public String toString() {
StringBuilder s = new StringBuilder();
for (Item item : this)
s.append(item + " ");
return s.toString();
}

// Return an iterator for stack
public Iterator<Item> iterator() {
return new ListIterator();
}

// an iterator, doesn't implement remove() since it's optional
private class ListIterator implements Iterator<Item> {
private Node current = first;
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }

public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}

// check internal invariants
private boolean check() {

// check a few properties of instance variable 'first'
if (n < 0) {
return false;
}
if (n == 0) {
if (first != null) return false;
}
else if (n == 1) {
if (first == null) return false;
if (first.next != null) return false;
}
else {
if (first == null) return false;
if (first.next == null) return false;
}

// check internal consistency of instance variable n
int numberOfNodes = 0;
for (Node x = first; x != null && numberOfNodes <= n; x = x.next) {
numberOfNodes++;
}
if (numberOfNodes != n) return false;

return true;
}
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.