Parsing expressions

You are going to write two methods: one translates expressions (Strings) from infix to postfix; the other evaluates postfix expressions.

The second one is easier, so you should do it first. Start by reading the handout and forming a development plan. Your plan should include at least three intermediate programs that you intend to write that do something testable.

It should also explain what built-in classes you intend to use. Hint: you will use Stacks, Strings, and possibly StringBuffers. For info about StringBuffers, check out the Sun web page and also Section 7.5 of Standish.

Hint: what should you do when you start working with a new class for the first time?

The hardest part of this assignment will be the READING. You will have to collect and assimilate information from at least three sources: the handout, Standish, and the Sun web pages.

• Start the reading EARLY (i.e. now).

• Write comments and highlight the important information so you can refer back to it quickly.

• If there are things you don't understand, have questions ready on Monday.

• If you are not sure about the details of how something works, write a short program to test it and write the results of your test back into the book.

When your program is finished, it should prompt the user to type an expression in infix, and it should translate into postfix, and then evaluate the expression.

Here is what the output should look like:

=>32+
32+
5
=>3+2*5
325*+
13

Notice that in the second example, the output is correct given that multiplication has higher precedence than addition.

Here is what the top-level loop for this program might look like. A good way to get started would be to type in this code and write mock-ups of translate and evaluate, then compile and run the program.

  public static void inputLoop () throws IOException {
    String s;
    BufferedReader stdin =
      new BufferedReader (
        new InputStreamReader (System.in));

    while (true) {
      System.out.print ("=>");
      String infix = stdin.readLine();
      if (infix == null) break;

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

      int res = evaluate (postfix);
      System.out.println (res);
    }
  }
  
  public static void main (String[] args) throws IOException {
    inputLoop ();
  }