Solution #10
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);
}
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);
}
}
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;
}
}
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;
}
}
}