Раскопки

Во время недавних раскопок на Марсе были обнаружены листы бумаги с таинственными символами на них. После долгих исследований учёные пришли к выводу, что надписи на них на самом деле могли быть обычными числовыми равенствами. Кроме того, из других источников было получено веское доказательство того, что марсиане знали только три операции - сложение, умножение и вычитание (марсиане никогда не использовали «унарный минус»: вместо «-5» они писали «0-5»). Также ученые доказали, что марсиане не наделяли операции разным приоритетом, а просто вычисляли выражения (если в них не было скобок) слева направо: например, 3+3*5 у них равнялось 30, а не 18. К сожалению, символы арифметических действий стерлись. Например, если была запись «18=7 (5 3) 2», то возможно восстановить эту запись как «18=7+(5-3)*2». Требуется написать программу, находящую требуемую расстановку знаков или сообщающую, что таковой не существует.

Входные данные

Первая строка входного файла INPUT.TXT состоит из натурального числа, не превосходящего 2³⁰, знака равенства, и последовательности натуральных чисел (не более десяти), произведение которых также не превосходит 2³⁰. Некоторые группы чисел (одно или более) могут быть окружены скобками. Длина входной строки не будет превосходить 80 символов, и других ограничений на количество и вложенность скобок нет. Между двумя соседними числами, не разделенными скобками, всегда будет хотя бы один пробел, во всех остальных местах может быть любое (в том числе и 0) число пробелов (естественно, внутри числа пробелов нет).

Выходные данные

В выходной файл OUTPUT.TXT необходимо вывести одну строку, содержащую полученное равенство (т.е., исходное равенство со вставленными знаками арифметических действий без лишних пробелов). В случае если требуемая расстановка знаков невозможна, вывести строку, состоящую из единственного числа «-1». Выходная строка не должна содержать пробелов.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]