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.