A201/A597 Introduction to Programming I (4/3 cr.)

CSCI A201/A597
Lab Notes Ten

Second Summer 2000

A simple (and very instructive) Java interpreter for arithmetic.

We start with a really simple evaluator.

import java.io.*;
import java.util.*;

public class EvalOne {
  public static void main(String[] args) {
    try { 
      BufferedReader in = new BufferedReader( 
                            new InputStreamReader(System.in));

      System.out.print("Eval> "); 
      String line = in.readLine();  

      while (! line.equals("exit")) {
        Vector v = new Vector(); 
        StringTokenizer s = new StringTokenizer(line); 
        while (s.hasMoreTokens()) v.addElement(s.nextToken()); 
        boolean done = false; 

        while (! done) {
          done = true; 
          done = reduceStars(v) && done; 
          done = reducePluses(v) && done; 
        } 

        printVector(v); 

        System.out.print("Eval> "); 
        line = in.readLine(); 
      } 
    } catch (Exception e) {
      System.out.println("E: " + e); 
    } 
  } 
  static boolean reduceStars(Vector v) {
    boolean done = true; 
    for (int i = 0; i <= v.size() - 1; i++) {
      if (v.elementAt(i).equals("*")) {
        int a = new Integer((String)v.elementAt(i - 1)).intValue(); 
        int b = new Integer((String)v.elementAt(i + 1)).intValue(); 
        int result = a * b; 
        v.removeElementAt(i + 1); 
        v.removeElementAt(i); 
        v.setElementAt(result + "", i - 1); 
        i = i - 1; 
        done = false; 
        printVector(v); // this shows the current state... 
      } 
    } 
    return done; 
  }
  static boolean reducePluses(Vector v) { // this cloned from reduceStars
    boolean done = true; 
    for (int i = 0; i <= v.size() - 1; i++) {
      if (v.elementAt(i).equals("+")) {
        int a = new Integer((String)v.elementAt(i - 1)).intValue(); 
        int b = new Integer((String)v.elementAt(i + 1)).intValue(); 
        int result = a + b; 
        v.removeElementAt(i + 1); 
        v.removeElementAt(i); 
        v.setElementAt(result + "", i - 1); 
        i = i - 1; 
        done = false; 
        printVector(v); 
      } 
    } 
    return done; 
  }

  static void printVector(Vector v) {
    for (int i = 0; i < v.size(); i++) {
      System.out.print(v.elementAt(i) + " "); 
    } System.out.println(); 
  }
}

And here's the program in action:

school.cs.indiana.edujava EvalOne
Eval> 1 + 2 + 3 + 4
3 + 3 + 4
6 + 4
10
10
Eval> 3 * 4 + 2 * 3 * 4
12 + 2 * 3 * 4
12 + 6 * 4
12 + 24
36
36
Eval> 3 * 3 * 3 * 3
9 * 3 * 3
27 * 3
81
81
Eval> exit
school.cs.indiana.edu

This only takes care of *'s and +'s and doesn't handle /'s, -'s or expressions involving parentheses.

The next program does handle all these things.

Notice how very similar it is to the one we wrote above.

import java.io.*;
import java.util.*;

public class EvalTwo {
  public static void main(String[] args) {
    try { 
      BufferedReader in = new BufferedReader(
                            new InputStreamReader(
                              System.in)); 
      System.out.print("EvalTwo> "); 
      String line = in.readLine(); 
      while (! line.equals("exit")) {
        Vector v = new Vector(); 
        StringTokenizer s = new StringTokenizer(line); 
        while (s.hasMoreTokens()) 
          v.addElement(s.nextToken()); 
        if (v.size() > 0) {
          boolean done = false; 
          while (! done) {
            done = true;
            done = reduceRedundantParens(v)  && done;   
            done = reduceStarsAndSlashes(v)  && done; 
            done = reducePlusesAndMinuses(v) && done;  
  	  } 
          System.out.print("Result is: "); 
          for (int i = 0; i < v.size(); i++) {
            System.out.print(v.elementAt(i) + " "); 
          } System.out.println(); 
        } else System.out.println(); 
        System.out.print("EvalTwo> "); 
        line = in.readLine(); 
      }
    } catch (Exception e) { 
      System.out.println("E: " + e); 
    } 
  } 
  static boolean reduceRedundantParens(Vector expr) {
    boolean done = true; 
    for (int i = 0; i < expr.size(); i++) {
      if (isValue((String)expr.elementAt(i))) {
        if (                    ((i - 1) >= 0         ) && 
            isLeftParen ((String)expr.elementAt(i - 1)) && 
                                ((i + 1) < expr.size()) && 
            isRightParen((String)expr.elementAt(i + 1))) 
        { 
          expr.removeElementAt(i + 1); 
          expr.removeElementAt(i - 1); 
          i = i - 1; 
          done = false; 
          printVector(expr); 
	}
      } 
    }    
    return done; 
  } 
  static boolean reduceStarsAndSlashes(Vector expr) {
    boolean done = true; 
    for (int i = 0; i < expr.size(); i++) {
      if (expr.elementAt(i).equals("*") ||
          expr.elementAt(i).equals("/")) {
        if (isValue((String)expr.elementAt(i - 1)) && 
            isValue((String)expr.elementAt(i + 1))) { 
          Integer a = new Integer((String)expr.elementAt(i - 1)); 
          Integer b = new Integer((String)expr.elementAt(i + 1)); 
          int result; 
          if (expr.elementAt(i).equals("*")) { 
            result = a.intValue() * b.intValue(); 
          } else { result = a.intValue() / b.intValue(); }
          String res = result + ""; 
          expr.removeElementAt(i + 1); 
          expr.removeElementAt(i); 
          expr.removeElementAt(i - 1); 
          expr.insertElementAt(res, i - 1); 
          i = i - 1; 
          done = false; 
          printVector(expr); 
	}
      } 
    } 
    return done; 
  } 
  static boolean reducePlusesAndMinuses(Vector expr) {
    boolean done = true; 
    for (int i = 0; i < expr.size(); i++) {
      if (expr.elementAt(i).equals("+") ||
          expr.elementAt(i).equals("-")) { 
        if (isValue((String)expr.elementAt(i - 1)) && 
            isValue((String)expr.elementAt(i + 1))) 
        { 
          Integer a = new Integer((String)expr.elementAt(i - 1)); 
          Integer b = new Integer((String)expr.elementAt(i + 1)); 
          int result; 
          if (expr.elementAt(i).equals("+")) { 
            result = a.intValue() + b.intValue(); 
          } else { result = a.intValue() - b.intValue(); } 
          String res = result + ""; 
          expr.removeElementAt(i + 1); 
          expr.removeElementAt(i); 
          expr.removeElementAt(i - 1); 
          expr.insertElementAt(res, i - 1); 
          i = i - 1; 
          done = false; 
          printVector(expr); 
	}
      } 
    }
    return done; 
  }
  static boolean isValue(String s) {
    return ! (s.equals("(") || s.equals(")"));  
  } 
  static boolean isLeftParen(String s) {
    return s.equals("(");  
  } 
  static boolean isRightParen(String s) {
    return s.equals(")"); 
  } 
  static void printVector(Vector v) {
    for (int i = 0; i < v.size(); i++) {
      System.out.print(v.elementAt(i) + " ");
    } System.out.println();
  }

}

And here's a session with it:

school.cs.indiana.edujava EvalTwo
EvalTwo> 1
Result is: 1 
EvalTwo> ( 1 + 2 ) * 3
( 3 ) * 3 
3 * 3 
9 
Result is: 9 
EvalTwo> ( 2 * 3 ) * ( 3 * 4 )
( 6 ) * ( 3 * 4 ) 
( 6 ) * ( 12 ) 
6 * ( 12 ) 
6 * 12 
72 
Result is: 72 
EvalTwo> ( ( ( 3 ) ) ) * 4
( ( 3 ) ) * 4 
( 3 ) * 4 
3 * 4 
12 
Result is: 12 
EvalTwo> ( 1 + 2 ) * 3 * ( 4 * 5 ) 
( 1 + 2 ) * 3 * ( 20 ) 
( 3 ) * 3 * ( 20 ) 
3 * 3 * ( 20 ) 
3 * 3 * 20 
9 * 20 
180 
Result is: 180 
EvalTwo> ( 2 - 3 ) + ( 10 / 2 )
( 2 - 3 ) + ( 5 ) 
( -1 ) + ( 5 ) 
-1 + ( 5 ) 
-1 + 5 
4 
Result is: 4 
EvalTwo> exit
school.cs.indiana.edu

What we still need to do is this:

include the ability to identify assignment statements
allow for identifiers to appear in expressions

store associations identifiers - values into a hashtable How you do it is up to you, but here are some hints:

One can easily identify an assignment statement: the second token is the = sign. Remember that your error checking is minimal.
If identifiers appear in expressions make a one-pass step that replaces the identifiers with their associated values (if any) in the hashtable before the evaluator starts. Remember that your error checking is minimal.

Use a Hashtable object to store associations.

Here's a sample solution for the evaluator.

Note that the code below handles *, +, -, /, (, ), assignment statements and algebraic expressions. A sample solution is presented below. Note also that you need to separate the tokens by spaces, i.e. (1 + 2) should be written as ( 1 + 2 ) because we use the default StringTokenizer settings.

oldschool.cs.indiana.edu%java Eval
  Eval> a = 1
  Stored 1 in a
  Eval> a = ( a + 1 ) * a
  ( 2 ) * 1 
  2 * 1 
  2 
  Stored 2 in a
  Eval> a 
  Result is: 2 
  Eval> a = ( a + 1 ) * a
  ( 3 ) * 2 
  3 * 2 
  6 
  Stored 6 in a
  Eval> a
  Result is: 6 
  Eval> exit

Here's the code. Notice how close it is to the one we started from.

import java.io.*;
import java.util.*;

public class Eval {
  public static void main(String[] args) {
    try { 
      Hashtable env = new Hashtable(); 
      BufferedReader in = new BufferedReader(
                            new InputStreamReader(
                              System.in)); 
      System.out.print("Eval> "); 
      String line = in.readLine(); 
      while (! line.equals("exit")) {
        Vector v = new Vector(); 
        StringTokenizer s = new StringTokenizer(line); 
        while (s.hasMoreTokens()) 
          v.addElement(s.nextToken()); 
        if (v.size() > 2 && v.elementAt(1).equals("=")) {
          String identifier = (String)v.elementAt(0); 
          v.removeElementAt(1); v.removeElementAt(0); 
          if (v.size() > 0) { substituteIdentifiers(env, v); 
            boolean done = false; 
            while (! done) { done = true;
              done = reduceRedundantParens(v)  && done;   
              done = reduceStarsAndSlashes(v)  && done; 
              done = reducePlusesAndMinuses(v) && done;  
    	    } 
            env.put(identifier, v.elementAt(0)); System.out.println(
              "Stored " + env.get(identifier) + " in " + identifier
            ); 
          } else System.out.println(); 
        } else { 
          if (v.size() > 0) {
            substituteIdentifiers(env, v); 
            boolean done = false; 
            while (! done) {
              done = true;
              done = reduceRedundantParens(v)  && done;   
              done = reduceStarsAndSlashes(v)  && done; 
              done = reducePlusesAndMinuses(v) && done;  
    	    } 
            System.out.print("Result is: "); 
            for (int i = 0; i < v.size(); i++) {
              System.out.print(v.elementAt(i) + " "); 
            } System.out.println(); 
          } else System.out.println(); 
        } 
        System.out.print("Eval> "); 
        line = in.readLine(); 
      }
    } catch (Exception e) { 
      System.out.println("E: " + e); 
    } 
  } 
  static void substituteIdentifiers(Hashtable env, Vector v) {
    for (int i = 0; i < v.size(); i++) { 
      char letter = ((String)v.elementAt(i)).charAt(0);
      if ((letter >= 'a' && letter <= 'z') || 
          (letter >= 'A' && letter <= 'Z')) {
        v.setElementAt(env.get(v.elementAt(i)), i); 
      } 
    } 
    printVector(v); 
  }
  static boolean reduceRedundantParens(Vector expr) {
    boolean done = true; 
    for (int i = 0; i < expr.size(); i++) {
      if (isValue((String)expr.elementAt(i))) {
        if (((i - 1) >= 0         )                     && 
            isLeftParen ((String)expr.elementAt(i - 1)) && 
            ((i + 1) < expr.size())                     && 
            isRightParen((String)expr.elementAt(i + 1))) { 
          expr.removeElementAt(i + 1); 
          expr.removeElementAt(i - 1); 
          i = i - 1; 
          done = false; 
          printVector(expr); 
	}
      } 
    }    
    return done; 
  } 
  static boolean reduceStarsAndSlashes(Vector expr) {
    boolean done = true; 
    for (int i = 0; i < expr.size(); i++) {
      if (expr.elementAt(i).equals("*") ||
          expr.elementAt(i).equals("/")) {
        if (isValue((String)expr.elementAt(i - 1)) && 
            isValue((String)expr.elementAt(i + 1))) { 
          Integer a = new Integer((String)expr.elementAt(i - 1)); 
          Integer b = new Integer((String)expr.elementAt(i + 1)); 
          int result; 
          if (expr.elementAt(i).equals("*")) { 
            result = a.intValue() * b.intValue(); 
          } else { 
            result = a.intValue() / b.intValue(); 
          }
          String res = result + ""; 
          expr.removeElementAt(i + 1); 
          expr.removeElementAt(i); 
          expr.removeElementAt(i - 1); 
          expr.insertElementAt(res, i - 1); 
          i = i - 1; 
          done = false; 
          printVector(expr); 
	}
      } 
    } 
    return done; 
  } 
  static boolean reducePlusesAndMinuses(Vector expr) {
    boolean done = true; 
    for (int i = 0; i < expr.size(); i++) {
      if (expr.elementAt(i).equals("+") ||
          expr.elementAt(i).equals("-")) { 
        if (isValue((String)expr.elementAt(i - 1)) && 
            isValue((String)expr.elementAt(i + 1))) { 
          Integer a = new Integer((String)expr.elementAt(i - 1)); 
          Integer b = new Integer((String)expr.elementAt(i + 1)); 
          int result; 
          if (expr.elementAt(i).equals("+")) { 
            result = a.intValue() + b.intValue(); 
          } else { result = a.intValue() - b.intValue(); } 
          String res = result + ""; 
          expr.removeElementAt(i + 1); 
          expr.removeElementAt(i); 
          expr.removeElementAt(i - 1); 
          expr.insertElementAt(res, i - 1); 
          i = i - 1; 
          done = false; 
          printVector(expr); 
	}
      } 
    }
    return done; 
  }
  static boolean isValue(String s) {
    return ! (s.equals("(") || s.equals(")"));  
  } 
  static boolean isLeftParen(String s) {
    return s.equals("(");  
  } 
  static boolean isRightParen(String s) {
    return s.equals(")"); 
  } 
  static void printVector(Vector v) {
    for (int i = 0; i < v.size(); i++) {
      System.out.print(v.elementAt(i) + " ");
    } System.out.println();
  }

}

By the end of this semester programs of this kind should be easy to read, write or think about.

Last updated: July 18, 2000 by Adrian German for A201

CSCI A201/A597 Lab Notes Ten

CSCI A201/A597
Lab Notes Ten