Задача g6_1088: Раскопки (Московская городская школьная олимпиада по программированию, заочный тур 2002-2003)

Во время недавних раскопок на Марсе были обнаружены листы бумаги с таинственными символами на них. После долгих исследований учёные пришли к выводу, что надписи на них на самом деле могли быть обычными числовыми равенствами. Если бы этот вывод оказался верным, это доказало бы не только то, что на Марсе много лет назад были разумные существа, но и то, что они уже умели считать:
Ученые смогли понять, что в этом случае означают найденные символы, и перевели эти равенства на обычный язык - язык цифр, скобок, знаков арифметических действий и равенства. Кроме того, из других источников было получено веское доказательство того, что марсиане знали только три операции - сложение, умножение и вычитание (марсиане никогда не использовали "унарный минус": вместо "-5" они писали "0-5"). Также ученые доказали, что марсиане не наделяли операции разным приоритетом, а просто вычисляли выражения (если в них не было скобок) слева направо: например, 3+3*5 у них равнялось 30, а не 18.
К сожалению, символы арифметических действий марсиане почему-то наносили специальными чернилами, которые, как оказалось, были не очень стойкими, и поэтому в найденных листках между числами вместо знаков действий были пробелы. Если вся вышеизложенная теория верна, то вместо этих пробелов можно поставить знаки сложения, вычитания и умножения так, чтобы равенства стали верными. Например, если был найден лист бумаги с надписью "18=7 (5 3) 2", то возможна такая расстановка знаков: "18=7+(5-3)*2" (помните про то, в каком порядке марсиане вычисляют выражения!). В то же время, если попался лист с надписью "5=3 3", то марсиане явно не имели в виду числового равенства, когда писали это:
Вы должны написать программу, находящую требуемую расстановку знаков или сообщающую, что таковой не существует.
Формат входных данных
Первая строка входного файла состоит из натурального (целого положительного) числа, не превосходящего 2³⁰, знака равенства, и последовательности натуральных чисел (не более десяти), произведение которых также не превосходит 2³⁰. Некоторые группы чисел (одно или более) могут быть окружены скобками. Длина входной строки не будет превосходить 80 символов, и других ограничений на количество и вложенность скобок нет. Между двумя соседними числами, не разделенными скобками, всегда будет хотя бы один пробел, во всех остальных местах может быть любое (в том числе и 0) число пробелов (естественно, внутри числа пробелов нет).
Формат выходных данных
В выходной файл необходимо вывести одну строку, содержащую полученное равенство (т.е., исходное равенство со вставленными знаками арифметических действий). В случае если требуемая расстановка знаков невозможна, вывести строку, состоящую из единственного числа "-1". Выходная строка не должна содержать пробелов.
Примеры
h.in
18=7 (5 3) 2
h.out
18=7+(5-3)*2
h.in
5=3 3
h.out
-1

Решение g6_1088:
Эту задачу можно решать множеством самых разнообразных способов, но мы остановимся на одном из самых простых, хотя, может быть, и не самом эффективном. Решение нашей задачи сводиться к рекурсивному перебору знаков - это не более 3₉ (менее 20000) вариантов и вычислению значения выражения для каждого варианта.
Именно задача вычисления выражения и является наиболее важной и трудоемкой. Мы воспользуемся модификацией так называемого "палочного метода" вычисления выражений. Для этого введем несколько правил замены. Т.е. если мы находим строку определенного вида, то заменяем ее на строку определенную правилом, поиск каждый раз начинаем с начала выражения.
'x+y' => 'z', где z=x+y
'x-y' => 'z', где x=x-y
'x*y' => 'z', где x=x*y
'(x)' => 'x'
Т.е. если мы встречаем два числовых операнда, между которыми стоит некоторый знак, то выделяем это выражение (назовем его "элементарным выражением", например, '12+35') и передаем его в процедуру, подчитывающую выражения такого простого вида (для примера она должна вернуть строку '47'), а затем заменяем в строке, содержащей выражение выделенную подстроку на результат вычислений. Если же встретился один числовой операнд, заключенный в скобки, то скобки следует удалить из строки - такое преобразование не изменяет значения выражения. Несложно проверить, что, используя эти правила, мы всегда получаем правильный результат.
Немного более подробно остановимся на алгоритме выделения элементарных выражений. Здесь можно воспользоваться методом конечных автоматов, введя автомат, имеющий следующие состояния:
1: жду начала выражения.
'0'..'9' - очищаем строку элементарного выражения, заносим текущий символ в строку элементарного выражения, переход в состояние 2.
другие символы - не выполняем никаких действий
2: ввод первого операнда.
'0'..'9' - добавляем текущий символ в строку элементарного выражения.
'+', '-', '*' - добавляем текущий символ в строку элементарного выражения, переход в состояние 3.
другие символы - переход в состояние 1.
3: проверка второго операнда.
'0'..'9' - добавляем текущий символ в строку элементарного выражения, переход в состояние 4.
другие символы - переход в состояние 1.
4: ввод второго операнда.
'0'..'9' - добавляем текущий символ в строку элементарного выражения.
другие символы - конец работы автомата, элементарное выражение найдено.

Автомат для удаления скобок, в которые заключен единственный операнд, написать еще проще.
Условие того, что выражение посчитано - не одно преобразование элементарного выражения не найдено. Т.е. осталось выражение вида 'x=y', где x и y - числа. Проверить его не представляет труда. В случае если равенство оказалось верным, следует вывести выражение с расставленными знаками (копию выражения, которое мы подсчитывали с помощью элементарных выражений).
Теперь об организации рекурсии. Вводимое выражение необходимо преобразовать, удалив все лишние пробелы, оставив только по одному пробелу между числами, перед скобкой и после скобки. Пробелы, перед первым и после последнего символа следует удалить.
Рекурсивная процедура должна искать в строке первый пробел, последовательно вставлять туда все возможные знаки и запускать следующую процедуру. В случае если пробелов найти не удалось, следует запускать проверку выражения. После работы процедуры на том месте, где она осуществляла вставку, следует восстанавливать пробел.
Теперь осталось только корректно обработать отсутствие решения.