/* 1992 ACM Finals, Problem A, Spreadsheet Calculator Ed Karrels, October 2007 */ import java.io.*; public class acm92a { // this is for making a linked list of positive or negative cell references public static class CellRef { int row, col; int sign; // 1 or -1 CellRef next; public CellRef(int row, int col, int sign) { this.row = row; this.col = col; this.sign = sign; } } public static class Cell { // the original expression for the cell String expression; // If the cell is an integer literal, that value. // If it's an expression, then this will be the sum of the integer // literals in the expression. int value; // a linked list of cell references in the expression. // if this cell is an iteger literal, this is null. CellRef references; // After Sheet.compute() is called, this will contain the computed // value, if this cell does not involve a circular referece. int computedValue; // During a traverse, set this to true while computing the dependencies // for this cell. If a cell with touched==true is reference, then // there is a circular reference. boolean touched; // Every cell that is found to depend on a circular reference // will be have isCircular set to true. boolean isCircular; // return index of the next character in 's' that is not a digit public static int nextNonDigit(String s, int fromPos) { while (fromPos < s.length()) { if (!Character.isDigit(s.charAt(fromPos))) return fromPos; } return s.length(); } // parse a cell value like "42" or "A2+B5-118" public Cell(String str) { this.expression = str; int pos = 0; char c = str.charAt(pos++); // integer literal if (c == '-' || Character.isDigit(c)) { value = str2int(str); } // expression else { int row = c - 'A'; c = str.charAt(pos++); int col = c - '0'; CellRef tailRef = references = new CellRef(row, col, 1); while (pos < str.length()) { c = str.charAt(pos++); int sign = c == '-' ? -1 : 1; c = str.charAt(pos++); if (Character.isDigit(c)) { int numEnd = nextNonDigit(str, pos); value += sign * str2int(str.substring(pos-1, numEnd)); pos = numEnd; } else { row = c - 'A'; c = str.charAt(pos++); col = c - '0'; tailRef.next = new CellRef(row, col, sign); tailRef = tailRef.next; } } } } public String toString() { return rightJustify(6, computedValue); } } // convert string to int, -1 on error public static int str2int(String str) { try { return Integer.parseInt(str); } catch (NumberFormatException e) { return -1; } } public static String rightJustify(int len, int val) { String valStr = Integer.toString(val); if (valStr.length() >= len) return valStr; StringBuffer buf = new StringBuffer(len); for (int totalLen=valStr.length(); totalLen < len; totalLen++) buf.append(' '); buf.append(valStr); return buf.toString(); } public static class Sheet { public Cell[][] cells; private boolean anyCircularRefs; public Sheet(int rows, int cols) { cells = new Cell[rows][]; for (int i=0; i < rows; i++) cells[i] = new Cell[cols]; } public void compute() { anyCircularRefs = false; for (int row=0; row < cells.length; row++) { for (int col=0; col < cells[row].length; col++) { computeCell(row, col); } } if (anyCircularRefs) { for (int row=0; row < cells.length; row++) { for (int col=0; col < cells[row].length; col++) { Cell cell = cells[row][col]; if (cell.isCircular) { System.out.println("" + ((char)('A'+row)) + ((char)('0'+col)) + ": " + cell.expression); } } } } else { // print column headers System.out.print(' '); for (int col=0; col < cells[0].length; col++) { System.out.print(rightJustify(6, col)); } System.out.println(); // print rows for (int row=0; row < cells.length; row++) { System.out.print((char)('A' + row)); for (int col=0; col < cells[row].length; col++) { System.out.print(cells[row][col]); } System.out.println(); } System.out.println(); } } public void computeCell(int row, int col) { Cell cell = cells[row][col]; if (cell.touched) { cell.isCircular = true; anyCircularRefs = true; return; } cell.computedValue = cell.value; if (cell.references == null) return; cell.touched = true; CellRef ref = cell.references; while (ref != null) { Cell refCell = cells[ref.row][ref.col]; computeCell(ref.row, ref.col); if (refCell.isCircular) { cell.isCircular = true; } else { cell.computedValue += ref.sign * refCell.computedValue; } ref = ref.next; } cell.touched = false; } } public static void main(String[] args) throws Exception { InputStream inStream = System.in; if (args.length > 0) inStream = new FileInputStream(args[0]); BufferedReader input = new BufferedReader(new InputStreamReader(inStream)); while (true) { String line = input.readLine(); String[] values = line.split(" "); int numRows = Integer.parseInt(values[0]); int numCols = Integer.parseInt(values[1]); if (numRows == 0 && numCols == 0) break; Sheet sheet = new Sheet(numRows, numCols); for (int row=0; row < numRows; row++) for (int col=0; col < numCols; col++) sheet.cells[row][col] = new Cell(input.readLine()); sheet.compute(); } } }