Nawiasy
Limit pamięci: 128 MB
Dany jest szablon wyrażenia arytmetycznego zawierający cztery podstawowe
działania, nawiasy oraz miejsca na liczby.
Na przykład (x*x)/(x+x) jest szablonem.
Wartościowaniem nazwiemy takie wstawienie liczb rzeczywistych do szablonu,
że wartość powstałego w ten sposób wyrażenia jest określona.
Wstawiając w kolejne miejsca powyższego przykładu, uzyskujemy wyrażenie
o wartości , natomiast wstawienie
nie jest wartościowaniem.
Jeśli zbiory wartościowań szablonów i są takie same
oraz dla każdego wartościowania wyrażenia powstałe z i
mają takie same wartości oraz szablon powstaje przez dodawanie i/lub
usuwanie nawiasów z szablonu ,
to mówimy, że szablony te są równoważne.
Na przykład szablony (x*x)/(x+x) i x*x/(x+x) są równoważne.
Szablony (x*x)/(x+x) i x*x/x+x nie są równoważne, bo wartościowanie
daje wyrażenia o wartościach i .
Szablony x-(x-x) i x-x+x nie są równoważne,
bo nie można jednego sprowadzić do drugiego przez dodawanie i usuwanie nawiasów.
Zadanie polega na znalezieniu szablonu o minimalnej liczbie nawiasów,
równoważnego danemu szablonowi.
Mnożenie i dzielenie mają ten sam priorytet,
większy niż dodawanie i odejmowanie; zatem mnożenie i dzielenie
jest wykonywane przed dodawaniem i odejmowaniem.
Dodawanie i odejmowanie mają ten sam priorytet.
Operacje o tym samym priorytecie są wykonywane od lewej do prawej.
Wejście
W pierwszym wierszu wejścia znajduje się liczba oznaczająca liczbę
wyrażeń.
W kolejnych wierszach znajdują się niepuste, poprawne szablony składające się
ze znaków +, -, *, /, (, ) i x (miejsca na liczby).
Suma długości wszystkich wyrażeń jest nie większa niż .
Wyjście
Na wyjściu należy wypisać wierszy. W -tym wierszu należy wypisać
szablon równoważny -temu szablonowi z wejścia, zawierający minimalną
liczbę nawiasów.
Przykład
Dla danych wejściowych:
2
x+(x+(x+x)-(x*x))/x
(x*x)/((x*x))+(x)
poprawną odpowiedzią jest:
x+(x+x+x-x*x)/x
x*x/(x*x)+x
Autor zadania: Tomasz Idziaszek.