Дано корректное математическое выражение, состоящее из переменных, обозначаемых строчными латинскими буквами, инфиксных бинарных операций и круглых скобок для группировки подвыражений. Все операции имеют ассоциативность слева направо и приоритеты, указанные в таблице:
Приоритет |
Операции |
1 (наибольший) |
*, / |
2 |
+, - |
3 |
& |
4 |
^ |
5 (наименьший) |
| |
Требуется удалить из выражения все лишние пары скобок, не влияющие на порядок операций в нём (операции трактовать абстрактно, без какого-либо математического смысла, опираясь только на формальный порядок операций). Приоритет определяет, в каком порядке выполняются операции в цепочке, а ассоциативность определяет направление вычислений в цепочке операций одного приоритета.
Ввод |
Вывод |
Замечания |
a+(b*c) |
a+b*c |
(у ‘*’ приоритет выше, чем у ‘+’, поэтому она и так выполняется первой,- скобки лишние); |
((a+b)+(c+d)) |
a+b+(c+d) |
(Скобки вокруг всего выражения допустимы, но никогда не влияют на порядок вычисления внутри. Поскольку ассоциативность всех операций слева направо, первые внутренние скобки лишние, а вторые – нет, без них выражение было бы эквивалентно (((a+b)+c)+d)); |
((a)+b)&c^d |
a+b&c^d |
(скобки вокруг переменной всегда лишние). |
(((a)&b^c|((d)))) |
a&b^c|d |
|
a |
a |
|
Формат входного файла:
Одна строка, содержащая исходное математическое выражение не длиннее 100 символов.
Формат выходного файла:
Одна строка с математическим выражением без лишних скобок.