Инфиксная в префиксную
Яап написал решение для лабораторного задания. Задача была довольно простой: преобразовать арифметическое выражение из инфиксной нотации в польскую (префиксную) нотацию. В инфиксной нотации операторы располагаются между операндами (например, 12 + 5), тогда как в префиксной нотации операторы стоят перед своими операндами (например, + 12 5).
Вот синтаксис выражения, которое Яап должен был преобразовать:
Expression ::= Number
| '(' Expression Op Expression ')'
| '(' '-' Expression ')'
Op ::= '+' | '-'
Number ::= Digit j Number Digit
Digit ::= '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'. Эта строка является выводом программы Яапа.
Выходные данные
Для каждого тестового случая выведите одну строку, содержащую два числа: наименьшее и наибольшее значение, которое можно получить при различных интерпретациях входного выражения.