Solution #10

10.1   Warming up

Do note that this section solution does not adhere to styling conventions.

private static Element find(Element element, String data) {

      if (element == null) {

            return null;

      }

      if (element.data.equals(data)) {

            return element;

      }

      return find(element.next, data);

}

 

public static int reverse(int n) {

      return reverse(n, 0);

}

 

private static int reverse(int n, int m) {

      if (n < 10) {

            return m * 10 + n;

      }

      m = (m * 10) + (n % 10);

      return reverse(n / 10, m);

}

 

10.2   The calculator parser

InvalidExpressionFormatException.java

package calc;

 

/**

 * This exception is thrown when a given arithmetic expression is identified

 * to have an invalid format.

 *

 * @author Boaz Kantor

 */

public class InvalidExpressionFormatException extends Exception {

     

      /**

       * Constructs a new exception object with the given message.

       * @param message the issue which caused this exception to be thrown.

       */

      public InvalidExpressionFormatException(String message) {

            super(message);

      }

}

 

ParseNote.java

package calc;

 

/**

 * Represents a node in a binary parse tree.

 * Every node supports data as String, and left/right children.

 *

 * @author Boaz Kantor

 */

class ParseNode {

     

      // instance variables

      private String data;

      private ParseNode left;

      private ParseNode right;

     

      /**

       * Constructs a new node with the given data.

       * @param data the node data (any value is valid)

       */

      public ParseNode(String data) {

            this.data = data;

            left = null;

            right = null;          

      }

     

      /**

       * Gets this node's data.

       * @return this node's data.

       */

      protected String getData() {

            return this.data;

      }

 

      /**

       * Gets this node's left child.

       * @return this node's left child.

       */

      protected ParseNode getLeft() {

            return left;

      }

 

      /**

       * Sets this node's left child.

       * @param left this node's left child.

       */

      protected void setLeft(ParseNode left) {

            this.left = left;

      }

 

      /**

       * Gets this node's right child.

       * @return this node's right child.

       */

      protected ParseNode getRight() {

            return right;

      }

 

      /**

       * Sets this node's right child.

       * @param right this node's right child.

       */

      protected void setRight(ParseNode right) {

            this.right = right;

      }

 

}

 

ParseTree.java

package calc;

 

/**

 * A utility class, which provides functionality of parsing an arithmetic

 * expression, and its equivalent ExpressionElement binary parse tree.

 *

 * @author Boaz Kantor

 */

public class ParseTree {

     

      /** Please ignore. Do not write a constructor. */

      public ParseTree() {}

     

      /**

       * Builds an expression binary parse tree out of the given arithmetic

       * expression.

       * The expression must be provided according to the following format

       * rules:<br>

       * 1. No whitespaces allowed.<br>

       * 2. Only binary operators are supported.<br>

       * 3. Operators must not be surrounded by parentheses.<br>

       * 4. Every operand must be surrounded by parentheses.<br>

       * Example:<br>

       * "(((2)+(10))/(3))+((5)+(-2))"

       * @param expression an arithmetic expression in the given format.

       * @return a reference to the root node of a parse tree, reflecting the

       * provided expression.

       * @throws InvalidExpressionFormatException when the given arithmetic

       * expression is identified to have an invalid format.

       */

      public static ParseNode buildTree(String expression)

                                                      throws InvalidExpressionFormatException {

           

            // validate parameters

            if (expression == null || expression.trim().length() == 0) {

                  throw new InvalidExpressionFormatException(

                              "Element is empty or null");

            }

           

            // check if it's a literal

            if (expression.charAt(0) != '(') {

                  if (!isDouble(expression)) {

                        throw new InvalidExpressionFormatException("Expected: literal");

                  }

                  return new ParseNode(expression);

            }

           

            // get to the middle (operator)

            int mid = getMiddleOperatorIndex(expression);

           

            // split the string

            String left = expression.substring(1, mid - 1);

            int rightIndex = expression.indexOf('(', mid);

           

            // validate format

            if (rightIndex == -1) {

                  throw new InvalidExpressionFormatException(

                              "Expected: open parenthesis");

            }

            if (rightIndex == expression.length() - 1) {

                  throw new InvalidExpressionFormatException(

                              "Expected: close parenthesis");

            }

           

            // continue splitting

            String operator = expression.substring(mid, rightIndex);

            String right = expression.substring(rightIndex + 1,

                        expression.length() - 1);

 

            // set nodes

            ParseNode node = new ParseNode(operator);

            node.setLeft(buildTree(left));

            node.setRight(buildTree(right));

           

            return node;

      }

     

      /**

       * Finds the middle operator of an expression string.

       * Since each operand must be enclosed in parentheses, the middle operator

       * is the only one that is not enclosed in parentheses.

       * @param expression

       * @return the index of the middle operator.

       * @throws InvalidExpressionFormatException

       */

      private static int getMiddleOperatorIndex(String expression)

                                                      throws InvalidExpressionFormatException {

            int parentheses = 1;

            int parenthesisIndex = 0;

           

            // count opening and closing parentheses

            while (parentheses > 0) {

                  parenthesisIndex++;     // before the loop there was an opening par.

                 

                  // see if we got to the end of the expression string

                  if (parenthesisIndex == expression.length()) {

                        throw new InvalidExpressionFormatException(

                                    "Invalid format: expected close parenthesis");

                  }

                 

                  // count parentheses

                  if (expression.charAt(parenthesisIndex) == '(') {

                        parentheses++;

                  } else if (expression.charAt(parenthesisIndex) == ')') {

                        parentheses--;

                  }

            }

           

            // 'index' now holds the closing parenthesis before the operator.

            return parenthesisIndex + 1;

      }

 

      /**

       * Converts a binary expression parse tree node to an ExpressionElement,

       * recursively.

       * @param root a non-null reference to the node to convert

       * @return a reference to the expression element reflected in the given

       * node, with operands as reflected by the element type and the node

       * children.

       * @throws IllegalArgumentException if the node is null or its data is

       * unsupported.

       */

      public static ExpressionElement toExpressionElement(ParseNode root)  {

           

            // validate parameter

            if (root == null) {

                  throw new IllegalArgumentException("Invalid node value: null");

            }

           

            String data = root.getData();

           

            // handle numeric nodes

            if (isDouble(data)) {

                  return new Literal(Double.parseDouble(data));

            }

           

            // recursively get the operands from the node's children

            ExpressionElement left = toExpressionElement(root.getLeft());

            ExpressionElement right = toExpressionElement(root.getRight());

           

            // build the operator according to the data

            if (data.equals(OperatorAdd.STRING_REPRESENTATION)) {

                  return new OperatorAdd(left, right);

            } else if (data.equals(OperatorSubtract.STRING_REPRESENTATION)) {

                  return new OperatorSubtract(left, right);

            } else if (data.equals(OperatorMultiply.STRING_REPRESENTATION)) {

                  return new OperatorMultiply(left, right);

            } else if (data.equals(OperatorDivide.STRING_REPRESENTATION)) {

                  return new OperatorDivide(left, right);

            }

           

            // if we got here, the data is not supported

            throw new IllegalArgumentException("Unsupported node data " + data);

      }

 

      /**

       * Finds out if a string includes a real number that can be converted to

       * a double.

       * @param string the number as string

       * @return true if the string includes a number, false otherwise

       */

      private static boolean isDouble(String string) {

            try {

                  Double.parseDouble(string.trim());

                 

                  // the string is a real number

                  return true;

                 

            } catch (NumberFormatException nfe) {

                 

                  // the string is not a number

                  return false;

            }

      }

}