Задача №220. Параллельные вычисления
Задано арифметическое выражение, содержащее операции сложения, умножения, круглые скобки и операнды, которыми являются буквы английского алфавита. Нас будет интересовать скорость вычисления таких выражений на многопроцессорной машине, поэтому скобки в них будем расставлять в обязательном порядке для указания порядка проведения операций.
Известно, что сложение двух чисел занимает время p, а умножение – время q. Время, необходимое для вычисления сложного выражения AoB, равно времени, затрачиваемому на выполнение операции o, плюс максимальное из двух чисел – времени вычисления подвыражения A и времени вычисления подвыражения B. Время вычисления операнда полагаем равным нулю. Требуется написать программу, которая:
1. Определяет время, необходимое для вычисления заданного выражения на многопроцессорной машине.
2. Находит эквивалентное заданному арифметическое выражение с минимальным временем вычисления и само это время.
Выражения называется эквивалентными, если одно из них можно получить из другого последовательностью следующих преобразований:
x + y → y + x , x * y → y * x (коммутативный закон),
x + (y + z) → (x + y) + z , x * (y * z) → (x * y) * z (ассоциативный закон).
В первой строке входных данных содержатся два целых числа p и q (1 ≤ p,q ≤ 1000), во второй – арифметическое выражение длиной не более 200 символов.
В первой строке выдайте ответ на первый вопрос задачи. Во вторую строку выведите эквивалентное заданному выражение с минимальным временем вычисления, а в третью – само это время.