0. Goals and Overview

The goal of this assignment is to practice using recursion, and to use recursion to rewrite expressions.

1. Defining Expressions

An expression consists of one or more sub-expressions called terms. If there are multiple terms, they are joined by additive operands such as + or -.

A term consists of one or more sub-expressions called factors. If there are multiple factors, they are joined by additive operands such as * or / or %.

A factor is either a constant, or a parenthesized sub-expression.

For this assignment (except for part 5), expressions will be formed only of single-digit constants, the operators +, -, *, /, %, and parentheses ( and ). Specifically, for this assignment expressions do not have spaces.

Every expression is a string, and with the above definition, every token in such expressions is a single character.

Some examples:

• "2+3*4" (evaluates to 14)
• "2+3%4" (evaluates to 1)
• "8-3-2-1" (evaluates to 2)
• "9/2%3" (evaluates to 1)

2. String Traversal

As part of this assignment, you must create an iterator that returns the characters of a string, one at a time. This is a specialized iterator that does not implement the standard Iterator interface. The outline of this iterator is:

public class HW9StringIterator {  // class variables   public HW9StringIterator(String s) {    // implementation of the constructor  }   public boolean hasNext() {    // implementation of hasNext  }   public char next() {    // implementation of next -- may throw exception  }   // back up by one position -- needed sometimes when parsing  public void backUp() {    // implementation of backUp -- throws exception if already at beginning  } }

3. Recursively Parsing Expressions

For this assignment, you must write recursive methods to read each of expression, term, factor, constant, and parenthesized subexpression.

Each of these methods must return a String containing the same expression, but in postfix order, that is, with each operator following its two operands (for this return String, you should use spaces to separate operands and operators). Using the above examples,

• if the String is "2+3*4", parseExp returns "2 3 4 * +"
• if the String is "2+3%4", parseExp returns "2 3 4 % +"
• if the String is "8-3-2-1", parseExp returns "8 3 - 2 - 1 -"
• if the String is "9/2%3", parseExp returns "9 2 / 3 %"

Since this program returns an equivalent expression that computes the same value but in a different format, this program is a compiler.

The argument to each of these methods is a HW9StringIterator si for which calling si.next() returns the next characters of the expression that has not yet been parsed.

All these methods recursively call each other if appropriate.

3.1 Example

Feel free to use this definition of parseTerm, and to model your parseExp, parseFactor, and parseParen after it, changing details as necessary.

public static String parseTerm(HW9StringIterator si) {  StringBuilder result = new StringBuilder();  if (! si.hasNext()) { /* error, print and throw an exception */ }  // the first thing we expect is an operand  // we immediately add it to the output postfix expression  result.add(parseFactor(si));  boolean done = false;  do {    // for a legal expression, after the operand we may see an operator,    // a closing parenthesis, or the end of the string    if (! si.hasNext()) {      break; // end of the string, we are done, exit the loop    }    char operator = si.next();    switch (operator) {      case '*': break;      case '/': break;      case '%': break;      // if we find a token that is not part of the factor,      // we back it up so that token can be processed by the method      // that called us      case '+': si.backUp(); done = true; break;      case '-': si.backUp(); done = true; break;      case ')': si.backUp(); done = true;  break;      default:  // error, print and throw an exception    }    if (! done) {      // now we read the second operand and add it to the result      result.add(" ");      result.add(parseFactor(si));      result.add(" ");      // now add the operator      result.add(operator);    }  } while (! done);  return result; }

4. Testing

Write suitable JUnit tests for all of the above.

This is done on java, thanks so much and comments on the code are appreciate, let me know of any clarification, thank you!