|
Название задачи: Электронная таблица . |
 |
Условие
Имеется таблица M × N, в каждой ячейке которой записано либо целое число, либо арифметическая формула. В формулах могут присутствовать целые числа, знаки *, /, +, -, (, ), пробелы и ссылки на значения из других ячеек таблицы, записываемые в виде {НомерCтроки, НомерCтолбца} (например, {1,10}). Требуется вычислить значения во всех ячейках заданной таблицы.Входные данные:
В первой строке входного файла записаны целые числа M и N (1 ≤ M, N ≤ 20). В каждой из последующих M строк содержится описание очередной строки таблицы. Описание состоит из целых чисел и арифметических формул, разделенных символами | (ASCII-код 124). Все числа принадлежат диапазону [-32768, 32767], а длина каждой формулы не превышает 100 символов.
Выходные данные:
Выведите в выходной файл значения всех ячеек таблицы. Значения ячеек каждой строки таблицы должны быть записаны через пробел в отдельной строке выходного файла. Все значения следует выводить с точностью до двух знаков после десятичной точки. Если значение ячейки вычислить невозможно, вместо него следует вывести символ - (ASCII-код 45).
Пример входного файла
2 3
1 | {1, 1 }*10 +3 | -{1,2}/{2,2}
{2,3} | 0 | {2,1}
Пример выходного файла
1.00 13.00 -
- 0.00 -
Решение
Скачать архив тестов и решенийКаждая ячейка в описываемом ниже процессе вычислений будет иметь один из следующих статусов: «еще не вычислялась», «вычисляется», «уже вычислялась, значение не может быть вычислено» и «уже вычислялась, значение известно».
Пусть нам требуется узнать значение какой-либо из ячеек, имеющей статус «еще не вычислялась». Меняем ее статус на «вычисляется» и производим синтаксический разбор формулы, записанной в ней. Для этого можно использовать метод рекурсивного спуска [Шень 95, гл. 13]. Если мы встретим ссылку на ячейку, имеющую статус «значение известно», то используем это значение. Если мы встретим ссылку на ячейку, имеющую статус «значение не может быть вычислено», то значение в анализируемой ячейке также не может быть вычислено и мы для нее устанавливаем тот же самый статус и заканчиваем разбор. Встретив ссылку на ячейку, значение которой еще не вычислялось, рекурсивно переходим к нахождению ее значения.
Рассмотрим, наконец, случай ссылки на ячейку со статусом «вычисляется». В этой ситуации мы обнаружили цикл из ссылок, который не может быть разрешен. Меняем статус анализируемой ячейки на «значение не может быть вычислено» и заканчиваем разбор.
В случае, когда значения всех ячеек, на которые ссылается текущая, были подсчитаны и в процессе разбора формулы не возникало делений на ноль, статус анализируемой ячейки меняется на «уже вычислялась, значение известно».
Легко видеть, что описанный процесс представляет собой обход в глубину графа, вершины которого соответствуют ячейкам таблицы, а ребра – ссылкам из одной ячейки на другую. Присваивание значений ячейкам происходит в том же порядке, что и присваивание новых номеров вершинам ациклического графа при выполнении топологической сортировки [Липский 88, п. 3.4; Кнут 76, п. 2.2.3].
