From Prefix to Postfix

Ο προθεματικός συμβολισμός (prefix notation) είναι μια μη συμβατική μορφή γραφής των αριθμητικών παραστάσεων. Στον τυπικό τρόπο γραφής των αριθμητικών παραστάσεων, γνωστό και ως ενδοθεματικό συμβολισμό (infix notation), ένας δυαδικός τελεστής τοποθετείται μεταξύ των τελεστέων, π.χ., ~3 + 4~, ενώ ο τελεστής στον προθεματικό συμβολισμό τοποθετείται πριν από τους τελεστέους, π.χ., ~+3\;4~.

Ομοίως, ο προθεματικός συμβολισμός για το ~5-2~ είναι ~-5\;2~. Μια ωραία ιδιότητα των προθεματικών εκφράσεων με δυαδικούς τελεστές είναι ότι δεν απαιτούνται παρενθέσεις καθώς δεν υπάρχει ασάφεια σχετικά με τη σειρά των πράξεων. Για παράδειγμα, η προθεματική αναπαράσταση της ~5-(4-2)~ είναι ~-5-4\;2~, ενώ η προθεματική αναπαράσταση της ~(5-4)-2~ είναι ~--5\;4\;2~. Ο προθεματικός συμβολισμός είναι επίσης γνωστός ως Πολωνική σημειογραφία (Polish notation), προς τιμήν του πολωνού λογικολόγου Jan Łukasiewicz, ο οποίος την επινόησε γύρω στο 1920.

Ομοίως, στον μεταθεματικό συμβολισμό (postfix notation) ή αλλιώς Αντίστροφη Πολωνική Σημειογραφία (Reverse Polish Notation – RPN) , ο τελεστής τοποθετείται μετά από τους τελεστέους. Για παράδειγμα, η μεταθεματική αναπαράσταση της έκφρασης ~(5-4)-2~ είναι ~5\;4-2-~.

Στόχος σας είναι να γράψετε ένα πρόγραμμα που θα μεταφράζει μια προθεματική αριθμητική έκφραση σε μεταθεματική.

Είσοδος

Κάθε γραμμή εισόδου περιέχει μια προθεματική αριθμητική έκφραση. Οι τελεστές είναι ~+~ και ~-~, και οι αριθμοί είναι όλοι μονοψήφιοι δεκαδικοί αριθμοί. Οι τελεστές και οι αριθμοί χωρίζονται με ακριβώς ένα διάστημα και επιπλέον οι γραμμές δεν θα ξεκινούν με διαστήματα. Το τέλος της εισόδου ορίζεται με το ~0~ σε μια ξεχωριστή γραμμή. Μπορείτε να υποθέσετε ότι κάθε γραμμή εισόδου περιέχει μια έγκυρη προθεματική αριθμητική έκφραση με λιγότερους από ~20~ τελεστές.

Έξοδος

Μεταφράστε κάθε έκφραση στη μεταθεματική αναπαράστασή της και εμφανίστε τες σε ξεχωριστές γραμμές. Οι αριθμοί και οι τελεστές θα πρέπει να χωρίζονται με τουλάχιστον ένα διάστημα. Το τελικό ~0~ δεν θα μεταφράζεται.

Παράδειγμα

input

1
+ 1 2
- 2 2
+ 2 - 2 1
- - 3 + 2 1 9
0

output

1
1 2 +
2 2 -
2 2 1 - +
3 2 1 + - 9 -