# Spreadsheet with reverse Polish equation solving

Interested to hear any suggestions on object orientation and style for this simple spreadsheet implementation. The spreadsheet contains cells with equations in reverse polish notation and has a solver method to either determine the cell values or throw an exception if a circular reference exists.

/**
* This class encapsulates a spreadsheet which is a collection of cells together
* with methods for solving the spreadsheet.
*/

private int nRows; // number of rows in the spreadsheet
private int nCols; // number of columns, must be less than or equal to 26
private ArrayList<Cell> cells; // the cells within the spreadsheet in row by row
// order

/**
* Construct a spreadsheet from a given expression array.
*
* @param nRows
*            number of rows in spreadsheet.
* @param nCols
*            number of columns in spreadsheet.
* @param exprArray
*            an array of Strings containing the expressions for the cells
*            of the spreadsheet specified in row by row order.
*/
public SpreadSheet(int nRows, int nCols, String... exprArray) {
this.nRows = nRows;
this.nCols = nCols;
cells = new ArrayList<Cell>(exprArray.length);
for (String expressionString : exprArray) {
}
}

/**
* Solve a spreadsheet and return the solution of each cell.
*
* @return array of doubles containing the solution to each cell in row by
*         row order.
* @throws CircularReferenceException if spreadsheet contains a circular reference.
*/
public Double[] dump() throws CircularReferenceException {
int validCells = 0; // cells with valid values
int validCellsPreviousIteration = 0; // cells with valid values in the
// previous iteration
try {
while (validCells < cells.size()) {
evaluate(); // evaluate each cell in the spreadsheet
validCells = countValidCells();
if (validCells == validCellsPreviousIteration) {
throw new CircularReferenceException(); // throw exception
// if number of
// cells that have
// valid values
// has not increased
} else {
validCellsPreviousIteration = validCells;
}
}
} catch (InvalidOperatorException e) {
System.out.println(e);
}
try {
return getValues();
} catch (InvalidValueException e) {
e.printStackTrace();
return null;
}
}

/**
* Retrieve cell from particular row and column of spreadsheet. Indexing is
* 0 based.
*
* @param row
*            row of cell.
* @param column
*            column of cell.
* @return cell at location (row,column).
*/
public Cell getCell(int row, int column) {
return cells.get(row * nCols + column);
}

/**
* Construct an array containing the value of each cell in the spreadsheet
* in row by row order.
*
* @return array of doubles containing values.
* @throws InvalidValueException
*/
private Double[] getValues() throws InvalidValueException {
Double[] values = new Double[cells.size()];
int i = 0;
for (Cell cell : cells) {
values[i++] = cell.getValue();
}
return values;
}

/**
* Count number of cells within the spreadsheet with valid values.
*
* @return number of cells with valid values.
*/
private int countValidCells() {
int validCells = 0;
for (Cell cell : cells) {
if (cell.isValueValid()) {
validCells++;
}
}
return validCells;
}

/**
* Evaluate the expression of every cell within the spreadsheet.
*
* @throws InvalidOperatorException
*/
private void evaluate() throws InvalidOperatorException {
for (Cell cell : cells) {
cell.evaluate();
}
}

/**
* Exception for when spreadsheet contains a circular reference.
*/
public class CircularReferenceException extends RuntimeException {
private static final long serialVersionUID = 1L;
}
}


Here is the Cell class:

/**
* This class encapsulates a single cell within a spreadsheet.
*/
public class Cell {

// necessary for resolving cell
// references
private String expression; // expression within cell in reverse Polish
// notation
private double value; // numerical value of evaluating expression
private boolean valueValid; // whether a valid value has been found so
// far. This will change from false to true
// once all cell references have been
// resolved, provided that there are no
// circular references

/**
* Constructor for a cell belonging to a particular spreadsheet.
*
*            SpreadSheet to which Cell belongs.
* @param expression
*            expression within cell.
*/
this.expression = expression;
}

/**
* Evaluates expression within a cell. Expression must be in reverse Polish
* notation.
*
* @throws InvalidOperatorException
*             if cell expression contains an invalid operator.
*/
public void evaluate() throws InvalidOperatorException {
if (!valueValid) { // prevent reevaluation of cells that have valid
// values
try {
// create stack containing terms in expression
Deque<String> expressionStack = new ArrayDeque<String>(
Arrays.asList(expression.split("\\s")));
value = evaluateRpn(expressionStack);
valueValid = true;
} catch (UnresolvedReferenceException e) {
// no action is necessary if a reference is unresolved, since it
// may be resolved at a later iteration during the solution of
}
}
}

/**
* Get value of a cell. This is the numerical value resulting from
* evaluating the cell's expression.
*
* @return numerical value resulting from evaluating cell's expression.
* @throws InvalidValueException
*             if a valid value is not currently available.
*/
public double getValue() throws InvalidValueException {
if (isValueValid()) {
return value;
} else {
throw new InvalidValueException();
}
}

/**
* Check if a valid numerical value has been evaluated for the cell. This
* will be true when evaluate() is called on the cell and all of the cell
* references in the cell's expression can be resolved.
*
* @return whether cell value is valid.
*/
public boolean isValueValid() {
return valueValid;
}

/**
* Evaluate an expression contained within an ExpressionStack.
*
* @param expressionStack
*            an expression represented as a stack of individual terms.
* @return evaluation of expression
* @throws InvalidOperatorException
* @throws UnresolvedReferenceException
*/
private double evaluateRpn(Deque<String> expressionStack)
throws InvalidOperatorException, UnresolvedReferenceException {
String term = expressionStack.removeLast();
if (isCellReference(term)) {
// if last term in expression is a cell reference then resolve it
return resolveCellReference(term);
} else {
double x, y;
try {
// if last term in expression is double then return it
x = Double.parseDouble(term);
} catch (NumberFormatException e) {
// otherwise last term is an operator, evaluate operands and
// apply operator
y = evaluateRpn(expressionStack);
x = evaluateRpn(expressionStack);
x = applyOperator(x, y, term);
}
return x;
}
}

/**
* Apply operator to operands x and y.
*
* @param x
*            first operand.
* @param y
*            second operand.
* @param operator
* @return result of operation
* @throws InvalidOperatorException
*/
private double applyOperator(double x, double y, String operator)
throws InvalidOperatorException {
if (operator.equals("+"))
return x + y;
else if (operator.equals("-"))
return x - y;
else if (operator.equals("*"))
return x *= y;
else if (operator.equals("/"))
return x / y;
else
throw new InvalidOperatorException(operator);
}

/**
* Resolve a reference to another cell within the spreadsheet. If the other
* cell has a valid value, then the value will be returned, otherwise an
* UnresolvedReferenceException will be thrown.
*
* @param reference
*            reference to another cell in the spreadsheet.
* @return value of referenced cell.
* @throws UnresolvedReferenceException
*/
private double resolveCellReference(String reference)
throws UnresolvedReferenceException {
int col = reference.charAt(0) - 'A';
int row = Integer.parseInt(reference.substring(1)) - 1;
try {
return referencedCell.getValue();
} catch (InvalidValueException e) {
throw new UnresolvedReferenceException();
}
}

/**
* Determine whether a term in an expression is a reference to another cell.
*
* @param term
* @return whether term is a cell reference.
*/
private boolean isCellReference(String term) {
return Character.isLetter(term.charAt(0));
}

/**
* Thrown to indicate than an invalid operator is specified in cell
* expression.
*/
public class InvalidOperatorException extends Exception {

private static final long serialVersionUID = 1L;
private String operator;

public InvalidOperatorException(String operator) {
this.operator = operator;
}

public String toString() {
return "Invalid operator " + operator;
}

}

/**
* Thrown to indicate that a cell reference cannot be resolved. This occurs
* if a valid value is not currently available for the referenced cell.
*/
public class UnresolvedReferenceException extends Exception {

private static final long serialVersionUID = 1L;

}

/**
* Thrown to indicate that getValue() was called on a cell with a value that
* is currently invalid.
*/
public class InvalidValueException extends Exception {

private static final long serialVersionUID = 1L;

}

}


1. private String expression; // expression within cell in reverse Polish
// notation
private double value; // numerical value of evaluating expression


I'd rename it to rpnExpression and evaluatedValue which will make the comments unnecessary. (Check Clean Code by Robert C. Martin, page 53-54 also.)

2. public Cell(SpreadSheet spreadsheet, String expression) {
this.expression = expression;
}


I'd check nulls here. checkNotNull from Guava is a gread choice for that. (Effective Java, 2nd edition, Item 38: Check parameters for validity)

3. if (!valueValid) { // prevent reevaluation of cells that have valid
// values


This condition is a good candidate for guard clause. References: Replace Nested Conditional with Guard Clauses in Refactoring: Improving the Design of Existing Code; Flattening Arrow Code

4. throw new InvalidValueException();


I'd put into the message the invalid expression.

5.  * @throws InvalidOperatorException
* @throws UnresolvedReferenceException


Are these lines necessary?

6. if (isCellReference(term)) {
// if last term in expression is a cell reference then resolve it
return resolveCellReference(term);
} else {
double x, y;
try {
// if last term in expression is double then return it
x = Double.parseDouble(term);
} catch (NumberFormatException e) {
// otherwise last term is an operator, evaluate operands and
// apply operator
y = evaluateRpn(expressionStack);
x = evaluateRpn(expressionStack);
x = applyOperator(x, y, term);
}
return x;
}


The isCellReference is a guard clause, so the else keyword and its parentheses are unnecessary:

if (isCellReference(term)) {
// if last term in expression is a cell reference then resolve it
return resolveCellReference(term);
}
double x, y;
try {
// if last term in expression is double then return it
x = Double.parseDouble(term);
} catch (NumberFormatException e) {
// otherwise last term is an operator, evaluate operands and
// apply operator
y = evaluateRpn(expressionStack);
x = evaluateRpn(expressionStack);
x = applyOperator(x, y, term);
}
return x;

7. Furthermore, I'd minimize the scope of the local variables:

try {
return Double.parseDouble(term);
} catch (NumberFormatException e) {
// otherwise last term is an operator, evaluate operands and
// apply operator
double y = evaluateRpn(expressionStack);
double x = evaluateRpn(expressionStack);
return applyOperator(x, y, term);
}
return x;


(Effective Java, 2nd edition, Item 45: Minimize the scope of local variables)

8. if (operator.equals("+"))


I prefer to invert the equals here:

if ("+".equals(operator))


It protects from NullPointerExceptions when the operator parameter is null.

9. } catch (InvalidValueException e) {
throw new UnresolvedReferenceException();
}


Usually it's a good practice to pass the cause to constructor of the new exception:

throw new UnresolvedReferenceException(e);

10. public InvalidOperatorException(String operator) {
this.operator = operator;
}

public String toString() {
return "Invalid operator " + operator;
}


I'd pass the "Invalid operator " + operator string to the constructor of the superclass (as the message) and omit the operator field:

public InvalidOperatorException(String operator) {
super("Invalid operator " + operator);
}


It's more common, and logging libraries will print the class name too, not just the string, which helps debugging.

Usually only a few cells of a spreadsheed are actually filled, so I'd suggest to use e.g. a Map<Point, Cell> to save memeory and to allow to use bigger spreadsheets.

I did not go in great detail, but it looks pretty good.

Just be careful with method names: dump() and evaluateRpn(). Usually abbreviations are avoided in Java.

I don't know if you should have made cells a two-dimensional List of List instead. It's a bit cleaner, but it's annoying when you want to loop over all cells. I guess you thought about it before deciding on a single array. Another option would be to define some Grid class that stores a List of List and that implements Iterable.

I would probably try to get the spreadsheet reference out of Cell. The evaluate methods would then need to be moved to SpreadSheet. I'm not sure that I really prefer that to the current implementation.

Another suggestion would be to use an Enum for the 4 operations. Yet again, I'm not sure it's a good idea, but you could look into it.

• Thanks! Actually dump() was the name required for external reasons, I don't particularly like it myself. Regarding evaluateRpn() do you think evaluateReversePolishNotation() would be better? – padawan Feb 11 '12 at 20:07
• Yes, I would use the full name. With IDE autocompletion you don't have to type the full names anyway. If you keep evaluateRpn, you'd better make it evaluateRPN. – toto2 Feb 11 '12 at 20:19
• Yes, I did think quite a bit about that. You're right, it would be more elegant to use a grid, or define a row class. I ended up going with a 1D list since this was the format that the input (the expressions) and the output (the values) are in, so it seemed more natural. – padawan Feb 11 '12 at 20:26
• @toto2: I would use the evaluateReversePolishNotation() but I think evaluateRpn is better than evaluateRPN. See Effective Java, 2nd edition, Item 56: Adhere to generally accepted naming conventions: "While uppercase may be more common, a strong argument can made in favor of capitalizing only the first letter: even if multiple acronyms occur back-to-back, you can still tell where one word starts and the next word ends. Which class name would you rather see, HTTPURL or HttpUrl?" – palacsint May 6 '12 at 10:53