92.
The following code implements a constructor for nonempty lists that takes a String representation of a list and parses it into a list, as described in Chapter 14. The parser used is a general-purpose parser for S-expressions. S-expressions (short for symbolic expressions) are built from a set of atomic elements (called atoms or symbols). Given the set of atoms, any S-expression is either an atom or a list of S-expressions. In order to avoid namespace clash with java.util, all S-expression classes (including List classes) are prepended with S. The constructor itself appears in class SCons. It also appears as a Factory method in class SExp. This code is also available online at http://www.cs.rice.edu/~eallen. Listing A-1: String-Parsing List Constructor
import java.util.*; interface StackI { /** * @ pre ! isEmpty() */ public Object top(); public Object pop(); public void push(Object o); public boolean isEmpty(); } class SExpParseException extends Exception { public SExpParseException(String msg) { super(msg); } } abstract class SExp { public static final String LEFT_PAREN = "("; public static final String RIGHT_PAREN = ")"; public static SExp parse(String tokens) throws SExpParseException { return parseSExp(new StringStack(tokens)); } public static SExp parseSExp(StackI tokens) throws SExpParseException { SExp nextSExp = parseNextSExp(tokens); if (tokens.isEmpty()) { // The stack of tokens consisted of a single S-expression // (with possible subexpressions), as expected. return nextSExp; } else { throw new SExpParseException("Extraneous material "+ "at end of stream."); } } public static SExp parseNextSExp(StackI tokens) throws SExpParseException { if (tokens.isEmpty()) { throw new SExpParseException("Unexpected end of token stream."); } else { // tokens.pop() succeeds Object next = tokens.pop(); if (next.equals(LEFT_PAREN)) { // The S-expression is a list. Accumulate the subexpressions // this list contains, and return the result. SList result = SEmpty.ONLY; while (! tokens.isEmpty()) { // tokens.pop() succeeds next = tokens.top(); if (next.equals(RIGHT_PAREN)) { // We've reached the end of the list. We need only // pop off the ending right parenthesis before returning. // Since subexpressions were accumulated in the front // of the list, we must return the reverse of the list // to reflect the proper structure of the S-expression. tokens.pop(); return result.reverse(); } else { // Recursively parse the next subexpression and // add it to result. result = new SCons(parseNextSExp(tokens), result); } } // If we haven't yet returned, then we've reached the end // of the token stream without finding the matching right // paren. throw new SExpParseException("Unmatched left parenthesis."); } else if (next.equals(RIGHT_PAREN)) { // A right parenthesis was encountered at the beginning of // the S-expression! throw new SExpParseException("Unmatched right parenthesis."); } else { // The next S-expression is an atom. return new Atom(next); } } } } class StringStack implements StackI { StringBuffer _values; public StringStack(String values) { _values = new StringBuffer(values); } public Object top() { if (_values.length() == 0) { throw new RuntimeException("Attempt to call top on an empty stack."); } else { // _values.length() >= 1 return new StringBuffer().append(_values.charAt(0)).toString(); } } public Object pop() { if (_values.length() == 0) { throw new RuntimeException("Attempt to pop an empty stack."); } else { // _values.length() >= 1 String result = new StringBuffer().append(_values.charAt(0)).toString(); _values.deleteCharAt(0); return result; } } public void push(Object o) { _values.append(o); } public boolean isEmpty() { return _values.length() == 0; } } abstract class SList extends SExp { abstract SList reverse(); /** * Although accessing first() and rest() is valid only on non-empty * lists, we can simplify many list-based operations by including * these accessors in the SList interface and then implementing them * in SEmpty with methods that throw exceptions. Since the alternative * would be to insert casts in many cases (such as the inner class * Iterator, below), this design does not decrease the effectiveness * of static checking. Additionally, the information provided during * an error at run-time is at least as informative. */ public abstract SExp first(); public abstract SList rest(); class Iterator { SList values; public Iterator() { values = SList.this; } public SExp next() { SExp result = values.first(); values = values.rest(); return result; } public boolean hasNext() { return !(values == SEmpty.ONLY); } } } class SEmpty extends SList { public static final SEmpty ONLY = new SEmpty(); private SEmpty() {} public String toString() { return "()"; } SList reverse() { return this; } public SExp first() { throw new RuntimeException("Attempt to access the first element "+ "of an empty list."); } public SList rest() { throw new RuntimeException("Attempt to access rest of an empty list."); } } class SCons extends SList { private SExp first; private SList rest; public SCons(SExp _first, SList _rest) { this.first = _first; this.rest = _rest; } /** * @pre SExp.parse(s) instanceof SCons */ public SCons(String s) throws SExpParseException { // Notice that the precondition guarantees that the cast // below will always succeed. SCons that = (SCons)SExp.parse(s); first = that.first(); rest = that.rest(); } public SExp first() {return this.first;} public SList rest() {return this.rest;} SList reverse() { SList result = SEmpty.ONLY; SList.Iterator iter = this.new Iterator(); while (iter.hasNext()) { result = new SCons(iter.next(), result); } return result; } public String toString() { StringBuffer result = new StringBuffer("("); SList.Iterator iter = this.new Iterator(); while (iter.hasNext()) { result.append(iter.next().toString()); } result.append(")"); return result.toString(); } } class Atom extends SExp { public Object value; public Atom(Object _value) { this.value = _value; } public String toString() { return value.toString(); } }
| |||||||||||||||||||||
