Задано арифметическое выражение, содержащее операции сложения, умножения, круглые скобки и операнды, которыми являются буквы английского алфавита. Нас будет интересовать скорость вычисления таких выражений на многопроцессорной машине, поэтому скобки в них будем расставлять в обязательном порядке для указания порядка проведения операций.
Известно, что сложение двух чисел занимает время p, а умножение — время q. Время, необходимое для вычисления сложного выражения AàB, равно времени, затрачиваемому на выполнение операции à, плюс максимальное из двух чисел — времени вычисления подвыражения A и времени вычисления подвыражения B. Время вычисления операнда полагаем равным нулю. Требуется написать программу, которая:
1. Определяет время, необходимое для вычисления заданного выражения на многопроцессорной машине.
2. Находит эквивалентное заданному арифметическое выражение с минимальным временем вычисления и само это время.
Выражения называются эквивалентными, если одно из них можно получить из другого последовательностью следующих преобразований:
· |
x + y Þ y + x |
|
(коммутативный закон) |
· |
x + (y + z)
Þ
(x + y) + z |
|
(ассоциативный закон) |
В первой строке входного файла содержатся два целых числа p и q (1 £ p, q £ 1000), во второй — арифметическое выражение длиной не более 200 символов.
Первая строка выходного файла должна содержать ответ на первый пункт задачи. Во вторую строку выведите эквивалентное заданному выражение с минимальным временем вычисления, а в третью — само это время.
1 1
((a+(b+(c+d)))*e)*f
5
((a+b)+(c+d))*(e*f)
3