Пусть имеется некоторый набор формул, задающих зависимости между переменными. Например, объём V пирамиды, в основании которой лежит прямоугольник со сторонами a=10 и b=15, а высота равна полусумме сторон основания, определяется следующим набором формул:

V = S*h / 3; S = a * b; a, b = 10, 15; h = (a + b) / 2

Обратите внимание на то, что каждая формула состоит из левой и правой частей, разделённых знаком «=». Левая часть является списком переменных, а правая часть – списком соответствующих этим переменным выражений. Переменные в левой части и выражения в правой части разделяются запятыми.

Формулы могут быть записаны в любом порядке, но, если в них нет циклических зависимостей, их можно расположить в порядке, в котором нужно выполнять вычисления.

Составьте программу, осуществляющую топологическую сортировку формул. В случае, если языком реализации программы выбран язык Java, то точкой входа в программу должен являться метод main класса FormulaOrder.

Для решения задачи нужно построить орграф, вершинами которого являются формулы, а дуги задают зависимости между ними. То есть, если формула vv зависит от формулы uu, то в графе существует дуга ⟨v,u⟩. Затем следует выполнить топологическую сортировку вершин этого орграфа, то есть расположить вершины в таком порядке, чтобы дуги вели от больших вершин к меньшим. Этот порядок, как не трудно догадаться, совпадает с порядком превращения «серых» вершин в «чёрные» в процессе обхода графа в глубину.

Формулы подаются в программу через стандартный потока ввода. Они отделяются друг от друга символом перевода строки. Выражения в составе формул содержат знаки четырёх арифметических операций, круглые скобки, десятичные числа и имена переменных. Имя переменной – это последовательность латинских букв и десятичных цифр, начинающаяся с буквы.

Программа должна выводить сообщение «syntax error», если какая-нибудь формула содержит синтаксическую ошибку, или если некоторая переменная присутствует в левой части нескольких формул, или если не существует формулы для вычисления какой-нибудь переменной.

Программа должна выводить сообщение «cycle» в случае обнаружения циклической зависимости формул. Для обнаружения циклической зависимости следует проверять наличие обратных дуг при обходе графа в глубину. Напомним, что обратная дуга ведёт в «серую» вершину.

Если ошибки в формулах не обнаружены, то программа должна выводить в стандартный поток вывода отсортированный набор формул. В случае существования нескольких вариантов взаимного расположения формул, требуется вывести любой из них.