Assignment 11 - Solution

List Processor Machines

Here's a minimal solution, that does not use the jumpstart.

tucotuco.cs.indiana.edu% more Homework11.java 
import java.io.*; 
import java.util.*; 
 
class Homework11 {
  public static void main(String[] args) {
    try {
 
      Hashtable env = new Hashtable();  // our environment 
 
      BufferedReader b = 
        new BufferedReader(
          new InputStreamReader(
            System.in));                // our reader 
 
      System.out.println("Welcome to the List Processor Machine."); 
 
      while (true) {
        System.out.print("input> "); 
        StringTokenizer s = new StringTokenizer(b.readLine()); 
        String cmd = ""; 
        if (s.hasMoreTokens()) { 
          cmd = s.nextToken(); 
 
          if        (cmd.equals("remove"))     { 
            String elem = s.nextToken(); 
            String from = s.nextToken(); 
            List list = makeList(s); 
            System.out.println(list.remove(elem));             
 
          } else if (cmd.equals("reverse"))    { 
            List list = makeList(s); 
            System.out.println(list.reverse());              
 
          } else if (cmd.equals("quit"))       { 
            System.out.println("Thanks for visiting. Good-bye."); 
            System.exit(0);
 
          } else if (cmd.equals("show"))       { 
            Enumeration e = env.keys(); 
            while (e.hasMoreElements()) {
              String key = (String)e.nextElement(); 
              String value = env.get(key).toString(); 
              System.out.println(key + " = " + value); 
            } 
 
          } else { // check for identifier 
            String var = cmd; 
            if (s.hasMoreTokens()) { 
              String temp = s.nextToken(); 
              if (temp.equals("=")) { // assignment 
                cmd = s.nextToken(); 

                if        (cmd.equals("remove"))    { 
                  String elem = s.nextToken(); 
                  String from = s.nextToken(); 
                  List list = makeList(s); 
                  env.put(var, list.remove(elem));     

                } else if (cmd.equals("reverse"))  { 
                  List list = makeList(s); 
                  env.put(var, list.reverse());     

                } else {
                   System.out.println("Incorrect assignment."); 
                } 

              } else {
                System.out.println("Incorrect statement."); 
              } 

            } else { 
              if (env.containsKey(cmd)) {
                System.out.println(env.get(cmd)); 

              } else { 
                System.out.println("Undefined: " + cmd); 
              } 
            } 
          } 
        } else {
          // empty line 
        } 
      } 
    } catch (Exception e) {
      System.out.println("Error: " + e.toString()); 
    } 
  } 

  static List makeList(StringTokenizer s) {
    if (s.hasMoreTokens()) {
      String elem = s.nextToken();
      return new List(elem, makeList(s)); 
    } else {
      return null; 
    } 
  } 
} 
 
class List {
  String  value; 
  List nextElement; 
  public String toString() {
    if (nextElement == null) {
      return value; 
    } else { 
      return value + " " + nextElement.toString(); 
    } 
  } 
  List(String value, List nextElement) {
    this.value = value; 
    this.nextElement = nextElement; 
  } 
  List reverse() {
    if (nextElement == null) { 
      return this; 
    } else {
      List temp = nextElement.reverse(); 
      temp.snoc(value); 
      return temp; 
    } 
  }
  void snoc(String value) {
    if (nextElement == null) {
      nextElement = new List(value, null); 
    } else {
      nextElement.snoc(value); 
    } 
  } 
  List remove (String val) {
    if (value.equals(val)) {
      if (nextElement == null) {
        return null;
      } else { 
        return this.nextElement.remove(val); 
      } 
    } else {
      if (nextElement == null) {
        return new List(value, null);
      } else { 
        return new List(value, this.nextElement.remove(val)); 
      } 
    } 
  } 
} 
tucotuco.cs.indiana.edu% 
And here's a sample session.

tucotuco.cs.indiana.edu% java Homework11
Welcome to the List Processor Machine.
input> show
input> a
Undefined: a
input> reverse a b c 
c b a
input> a = reverse 1 2 3
input> a
3 2 1
input> show
a = 3 2 1
input> remove 3 from 1 2 3 1 2 3 1 2 3      
1 2 1 2 1 2
input> b
Undefined: b
input> b = remove a from a b b a 
input> b
b b
input> show 
b = b b
a = 3 2 1
input> quit
Thanks for visiting. Good-bye.
tucotuco.cs.indiana.edu% 
It was not necessary to implement show.

The jumpstart solution was also OK and a few students have come up with non-recursive solutions of their own. Congratulations to those of you who turned in solutions that were not based on the posted jumpstart and instead worked out an own idea!