CS231 lecture notes, Fall 1998
Week 8, Wednesday

1) Started with Eval

2) Found two ways to convert characters to integers:

    for (int i=0; i<line.length(); i++) {
      String s = line.substring(i,i+1);
      System.out.print (Integer.valueOf(s)+".");
      int value = (int)(line.charAt(i) - '0');
      System.out.print (value);
    } 

3) Tested isDigit

4) Wrote isOperator

5) Identified the characters in a String

    for (int i=0; i<line.length(); i++) {
      char c = line.charAt(i);

      if (Character.isDigit (c)) {
	System.out.println ("Operand");
      } else if (isOperator (c)) {
	System.out.println ("Operator");
      } else {
	System.out.println ("Error");
      }
    }

And tested it

=>123+?
Operand
Operand
Operand
Operator
Error

=>1+-\*/
Operand
Operator
Operator
Error
Operator
Operator


6) Wrote precedence and outranks

  public static int precedence (char c) {
    switch (c) {
    case '+': case '-':
      return 0;
    case '*': case '/':
      return 1;
    default:
      System.out.println ("Error in precedence: non-operator");
      System.exit(1);
    }    
  }

  public static boolean outranks (char c, char d) {
    return (precedence(c) > precedence (d));
  }

They compile, but I didn't bother testing them.  Lazy.

7) Copy a String into a StringBuffer

    StringBuffer out = new StringBuffer (line.length());

    for (int i=0; i<line.length(); i++) {
      out.append (line.charAt(i));
    }
    System.out.println (out);

That worked.

8) Implement the expression evaluator.  At this point I did an evil
   thing and skipped way too many steps, but I got something that
   mostly worked, although it took a little while to compile:

  public static int evaluate (String line) {
    Stack stack = new Stack ();

    for (int i=0; i<line.length(); i++) {
      char c = line.charAt(i);

      if (Character.isDigit (c)) {
	int operand = charToInt (c);
	stack.push (new Integer (operand));
      } else if (isOperator (c)) {
	int op2 = ((Integer) stack.pop()).intValue();
	int op1 = ((Integer) stack.pop()).intValue();
	int res = operate (op1, op2, c);
	stack.push (new Integer (res));
      } else {
	System.out.println ("Error");
      }
    }
    int res = ((Integer) stack.pop()).intValue();
    return res;
  }

I tested a few cases and they worked.

9) I implemented a simplified version of the translator that doesn't
handle parentheses.

  public static StringBuffer translate (String line) {
    StringBuffer out = new StringBuffer (line.length());
    Stack stack = new Stack ();

    for (int i=0; i<line.length(); i++) {
      char c = line.charAt(i);

      if (Character.isDigit (c)) {
	out.append (c);
      } else if (isOperator (c)) {
	dealWithOperator (c, out, stack);
      } else {
	System.out.println ("Error");
      }
    }
    return out;
  }

I factored out dealWithOperator just because I expected the syntax
to be ugly.

  public static void dealWithOperator (char c, StringBuffer out, Stack stack) {
    if (stack.empty()) {
      stack.push (new Character (c));
      return;
    }
    char pendingOperator = ((Character) stack.pop()).charValue();
    System.out.println (pendingOperator);
  }

I started with a test version of dealWithOperator that just checked the
operator stack.  It worked.

10) Now I went for the whole enchilada (without parentheses).  I took
me a while to untangle the book's presentation of the logic, but when
I did I got the following:

  public static void dealWithOperator
    (char operator, StringBuffer out, Stack stack) {

    while (!stack.empty()) {
      char pending = ((Character) stack.peek()).charValue();
      if (outranks (operator, pending)) {
	break;
      } else {
	pending = ((Character) stack.pop()).charValue();
	out.append (pending);
      }
    }
    stack.push (new Character (operator));
    return;
  }

Notice the use of peek to avoid having to put things back on the stack
if they turn out wrong.

Also, at the end of translate:

    while (!stack.empty()) {
      char operator = ((Character) stack.pop()).charValue();
      out.append (operator);
    }

That is, print all the leftover operators at the end.

11) Now let's add parentheses:

  public static void dealWithCloser (StringBuffer out, Stack stack) {
    while (!stack.empty()) {
      char pending = ((Character) stack.peek()).charValue();
      if (pending == '(') break;

      pending = ((Character) stack.pop()).charValue();
      out.append (pending);
    }
  }

  public static void dealWithOperator
    (char operator, StringBuffer out, Stack stack) {

    while (!stack.empty()) {
      char pending = ((Character) stack.peek()).charValue();
      if (pending == '(') break;

      if (outranks (operator, pending)) {
	break;
      } else {
	pending = ((Character) stack.pop()).charValue();
	out.append (pending);
      }
    }
    stack.push (new Character (operator));
    return;
  }

  public static StringBuffer translate (String line) {
    StringBuffer out = new StringBuffer (line.length());
    Stack stack = new Stack ();

    for (int i=0; i<line.length(); i++) {
      char c = line.charAt(i);

      if (Character.isDigit (c)) {
	out.append (c);
      } else if (isOperator (c)) {
	dealWithOperator (c, out, stack);
      } else if (c == '(') {
	stack.push (new Character (c));
      } else if (c == ')') {
	dealWithCloser (out, stack);
      } else {
	System.out.println ("Error unknown character:" + c);
      }
    }
    while (!stack.empty()) {
      char operator = ((Character) stack.pop()).charValue();
      out.append (operator);
    }
    return out;
  }

That's what I've got so far.  Here are some tests:

=>1+2-3  
12+3-
=>1+2*3
123*+
=>1*(2+3)
123+(*

Oops, that last one doesn't look so good.  I think in dealWithCloser
I should not be peeking at the open parenthesis; I should go ahead
and pop it:

  public static void dealWithCloser (StringBuffer out, Stack stack) {
    while (!stack.empty()) {
      char pending = ((Character) stack.pop()).charValue();
      if (pending == '(') break;
      out.append (pending);
    }
  }

That did it!

12) Last step is to put it all together:

Have to change evaluate to take a StringBuffer instead of a String.

      StringBuffer postfix = translate (infix);
      System.out.println (postfix);
      int res = evaluate (postfix);
      System.out.println (res);