Algorithmen Übungen WS13/14

Jugendliche geben jede Menge Geld aus für Dinge wie Süßigkeiten, Musik-CDs und Handys. Dabei haben sie allerdings das Problem, dass ihr Taschengeld nicht ausreicht für all diese begehrten Dinge.

Lisa Listig ist eines dieser armen Mädchen mit zu wenig Taschengeld. Letzten Monat war ihr Taschengeld schon nach einer Woche verbraucht. Deshalb trat sie in Verhandlungen mit ihrem Vater. Ihr Vater Tomm - ein Mathematiker - hatte eine unglaublich raffinierte Idee: Er schrieb einen arithmetischen Ausdruck bestehend aus einzelnen Ziffern, die durch die Operationen '+' bzw. '*' getrennt waren, auf ein Papier und sagte Lisa, ihr Taschengeld werde um X Euro erhöht, wobei X das Ergebnis der Rechnung sei.

Lisa machte sich sofort an die Arbeit, X zu berechnen. Dabei fiel ihr auf, dass durch geschicktes Setzen von Klammern ein sehr großer Wert erreicht werden konnte. Lisa bestimmte auf diese Weise den maximalen Wert, den man durch Klammerung der Operationen erreichen konnte. Allerdings hatte sie die Rechnung ohne ihren Vater gemacht: Er klammerte ebenfalls die Operationen, und zwar so, dass das Ergebnis der Rechnung minimiert wurde.

Ihre Aufgabe ist es, die Ergebnisse zu bestimmen, die Lisa bzw. ihr Vater berechnet haben.

Eingabe

Die erste Zeile der Eingabe enthält die Anzahl der Testfälle k (k < 5000). In jeder der folgenden k Zeilen ist ein arithmetischer Ausdruck gegeben. Dieser Ausdruck besteht aus den Ziffern 0 - 9 getrennt von einer der Operationen '+' bzw. '*'. Jede Zeile enthält zwischen 1 und 99 Zeichen.

Ausgabe

Geben Sie für jeden Ausdruck eine Zeile mit zwei Zahlen aus, wobei die erste Zahl das Ergebnis von Lisa, die zweite Zahl das Ergebnis ihres Vaters ist. Die Ergebnisse aller Rechnungen sind kleiner als 2³¹.

Beispiel

Eingabe:
2
9+0*1+3*0+1
1+2*3+4*5
Ausgabe:
36 1
105 27

Mögliche Klammerungen für die Beispiele:

((9+0)*(1+3))*(0+1) = 36
(((9+0)*(1+3))*0)+1 =  1
((1+2)*(3+4))*5 = 105
1+((2*3)+(4*5)) =  27