Інфікс до Префікс
Jaap написав розв'язок для лабораторного завдання. Завдання було досить простим: перетворити арифметичний вираз у інфіксній нотації на вираз у польській (префіксній) нотації. У інфіксній нотації оператори записуються між операндами (наприклад, 12 + 5), тоді як у префіксній нотації оператори розміщуються ліворуч від своїх операндів (наприклад, + 12 5).
Ось синтаксис виразу, який Яап мав перетворити:
Вираз ::= Число
| '(' Вираз Оп Вираз ')'
| '(' '-' Вираз ')'
Оп ::= '+' | '-'
Число ::= Цифра j Число Цифра
Цифра ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
Якщо Число має більше однієї цифри, воно не починатиметься з '0'.
Число має не більше 9 цифр.
На цьому етапі ми повинні визнати, що завдання було не дуже добре визначене. Більш конкретно, синтаксис отриманого виразу не був заданий. Тому Яапу довелося приймати деякі рішення самостійно — і він прийняв неправильні рішення.
Це була його перша помилка: він вважав, що у префіксній нотації пробіли є зайвими. Це правда в інфіксній нотації, оскільки завжди буде оператор між двома числами. У префіксній нотації, однак, числа повинні бути відокремлені одне від одного. Пропуск пробілів у префіксній нотації, як це зробив Яап, призводить до виразів на кшталт +1234, які мають три різні інтерпретації. (Вправа: намалюйте три різні синтаксичні дерева.)
Це була друга помилка Яапа: він вважав, що у префіксній нотації дужки є зайвими. Префіксна нотація без дужок є однозначною лише якщо арність операторів фіксована. Двозначність виникає, наприклад, у присутності як унарного, так і бінарного мінуса. Вираз: –34, може бути прочитаний як (- (- 3 4)), що обчислюється до 1, або як (- (- 3) 4), що обчислюється до -7, і навіть як (- (- 34)), що обчислюється до 34.
Ми не просимо вас відновити програму Яапа. Ми просимо вас з'ясувати, наскільки двозначним є його вихід.
Вхідні дані
Кожен тестовий випадок складається з одного рядка з непорожнім рядком довжиною ≤ 1000. Рядок містить лише символи '+' та '-' і цифри '0' до '9'. Цей рядок є виходом програми Яапа.
Вихідні дані
Для кожного тестового випадку виведіть один рядок, що містить два числа: найменше та найбільше значення, яке можна отримати за різними інтерпретаціями вхідного виразу.