Help with Optional Lab Fourteen (August 2)

Here's a program we will write and discuss in class:

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:

frilled.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
frilled.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 ones we wrote above.

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("EvalOne> "); 
      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("EvalOne> "); 
        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:

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

What you 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:
1. One can easily identify an assignment statement: the second token is the = sign. Remember that your error checking is minimal.
2. 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.
3. Use a Hashtable object to store associations.
  Please let us know if you have any questions.
  Disclaimer: you do not need to implement things the way we described them above, but if this helps you think about how the problem can be solved feel free to use any of it.