<ПРЕД Задача:
СЛЕД>
Задачу решили 27 пользователей: daniel.ugra, sridhar87, tomek, ethanhunt, dan, marek.cygan, tnsantosh, nishant, vviswa, scholl, e2n, LoLitter, JohnJones_001, Rizvanov, tourist, pmnox, vi002, WsemirZ, zloy_mipt, mazahaka, UdH-WiNGeR, Fat, Kuznetsov_S, defrager, RAVEman, Dest, EAA2008.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Расстановщик скобок

Time limit = 5 секунд(ы)

Математические выражения состоят из операторов и операндов. В свою очередь некоторые операторы, такие как '+', '-', '*', обладают свойством ассоциативности, т.е. для любых чисел а, b, c справедливо следующее: a + (b + c) = (a + b) + c, а некоторые не обладают этим свойством, например, оператор '/': (a / b) / c ≠ a / (b / c). Поэтому вводится понятие левой и правой ассоциативности. В языках программирования каждый из операторов имеет определенный приоритет и ассоциативность.

Пусть у нас есть следующий набор операторов:

ПриоритетАссоциативностьОператорОписание
1права^возведение в степень
2левая*умножение
2левая/деление
3левая+сложение
3левая-вычитание
и выражение 1+2*3-4/5/6*7^9^10+(7*8-1).

Нам нужно расставить в нем скобки. Построим дерево вычислений:

Отсюда хорошо видно, что ответ единственен: (((1+(2*3))-(((4/5)/6)*(7^(9^10))))+((7*8)-1))

Вход На вход подаются строки. Первая часть строк описывает операторы. Операторы, стоящие на одной строке имеют равные приоритеты. Строки идут в порядке возрастания приоритета содержащихся в них операторов. Каждая строка начинается с типа ассоциативности (LEFT, RIGHT) содержащихся в ней операторов, после чего (через пробел) перечислены операторы.

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

После описания операторов следует одна строка, начинающаяся со слова ALPHABET, со списком символов, из которых могут состоять операнды.

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

Длина выражения не превосходит 310000.

Выход Одна строка, содержащая выражение, с расставленными в нём скобками. Число пар скобок должно совпадать с числом бинарных операторов.

Вход#1
LEFT + -
LEFT * /
RIGHT ^
ALPHABET 0123456789
1+((2))*3-4/(5)/6*7^9^10+(7*8-1)
Выход#1
(((1+(2*3))-(((4/5)/6)*(7^(9^10))))+((7*8)-1))

Вход#2
RIGHT =
RIGHT * /
ALPHABET abcdefghijklmnop
a=b=c=d*e*f*g*h/i/j/k/l
Выход#2
(a=(b=(c=(d*(e*(f*(g*(h/(i/(j/(k/l)))))))))))
Вход#3
LEFT ,
RIGHT = += *= 
LEFT + -
LEFT * /
RIGHT ^
ALPHABET 0123456789abcdefghijklmnop
abc=f,a=b+c+d/1/2/3,e+=f+=g+=add*4*5+6*7*8-9-10
Выход#3
(((abc=f),(a=((b+c)+(((d/1)/2)/3)))),(e+=(f+=(g+=(((((add*4)*5)+((6*7)*8))-9)-10)))))

Автор:
Классическая задача. Тесты и описание -- Татьяна Зиновьева.
07 декабря 2006

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 18.207.240.35