Spreadsheet Circular Reference
Time limit1sMemory limit128 MB
Given spreadsheet cell formulas as lines, decide for each defined cell whether evaluating it leads to a circular reference, printing the cell name and circular or ok.
Problem
Determine whether a spreadsheet's formula definitions can be evaluated consistently.
Any cell of a spreadsheet may hold a formula that depends on the value of some other cell. Before actually computing a cell's value, it is important to determine whether that cell's formula definition is circular.
The spreadsheet supports only a limited grammar for expressions:
definition := cell "=" expression
expression := term | expression "+" term | expression " " term
term := factor | term "*" factor | term "/" factor
factor := number | cell | "(" expression ")"
number := digit | number digit
digit := "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
cell := "R" digit digit "C" digit digit
A cell's row and column numbers are each valid from 1 through 20, so the spreadsheet contains a total of 400 cells.
To compute a cell's value, the values of every cell that its formula references are needed. If computing a cell ever requires its own value again — directly or indirectly — then that cell's definition is circular.
Input
The input consists of one or more lines. Each line represents one cell defined in the spreadsheet and follows the definition rule of the grammar above, i.e. the form cell=expression.
Output
For each cell defined in the input, print one line, in the same order the cells appear in the input. Each line contains the cell name, followed by a single space and then circular if evaluating that cell leads to a circular definition (directly or indirectly), or ok if the cell can be evaluated without any circular definition.