스프레드시트 순환 참조

스프레드시트의 수식 정의가 모순 없이 계산될 수 있는지 판별한다.

스프레드시트의 각 셀에는 다른 셀의 값을 참조하는 수식이 들어갈 수 있다. 어떤 셀의 값을 실제로 계산하기 전에, 그 셀의 수식 정의가 순환(circular)인지 먼저 확인해야 한다.

이 스프레드시트가 다루는 수식(expression)의 문법은 다음과 같이 제한된다.

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

셀의 행과 열 번호는 각각 1부터 20까지 유효하므로, 스프레드시트에는 모두 400개의 셀이 존재한다.

한 셀의 값을 계산하려면 그 수식이 참조하는 모든 셀의 값이 필요하다. 만약 어떤 셀을 계산하는 과정에서 (직접적으로든 간접적으로든) 자기 자신의 값이 다시 필요해지면, 그 셀의 정의는 순환이다.

입력은 한 줄 이상으로 이루어지며, 각 줄은 스프레드시트에 정의된 하나의 셀을 나타낸다. 각 줄은 위 문법의 definition 형식, 즉 cell=expression 꼴이다.

입력에 정의된 각 셀에 대해, 입력에 나타난 순서 그대로 한 줄씩 출력한다. 각 줄에는 먼저 셀 이름을 쓰고, 그 셀을 계산할 때 (직접 또는 간접적으로) 순환 정의가 발생하면 circular를, 순환 없이 계산할 수 있으면 ok를 셀 이름 뒤에 한 칸 띄어 출력한다.