중위 표기식을 전위 표기식으로

Jaap이 실습 과제로 프로그램을 하나 만들었다. 과제는 간단했다. 중위 표기법으로 쓴 산술식을 폴란드 표기법(전위 표기법)의 식으로 바꾸는 것이다. 중위 표기법은 연산자를 두 피연산자 사이에 쓰고(12 + 5), 전위 표기법은 연산자를 피연산자 왼쪽에 쓴다(+ 12 5).

Jaap이 변환해야 했던 식의 문법은 다음과 같다.

Expression ::= Number
            |  '(' Expression Op Expression ')'
            |  '(' '-' Expression ')'
Op         ::= '+' | '-'
Number     ::= Digit | Number Digit
Digit      ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

두 자리 이상인 Number는 0으로 시작하지 않는다. Number는 아무리 길어도 9자리다.

여기서 과제 설명이 부실했다는 점은 인정해야 한다. 결과 식의 문법을 알려 주지 않았으니 Jaap이 직접 정할 수밖에 없었고, 그는 잘못된 쪽을 골랐다.

첫 번째 실수는 전위 표기법에서 공백이 필요 없다고 믿은 것이다. 중위 표기법에서는 두 수 사이에 항상 연산자가 있으니 공백을 빼도 되지만, 전위 표기법에서는 수와 수를 갈라 주어야 한다. Jaap처럼 공백을 모두 빼면 +1234 같은 식이 나오고, 이 식은 세 가지로 읽힌다. (연습: 서로 다른 구문 트리 세 개를 그려 보자.)

두 번째 실수는 전위 표기법에서 괄호가 필요 없다고 믿은 것이다. 괄호 없는 전위 표기법은 연산자의 항수가 고정되어 있을 때만 뜻이 하나로 정해진다. 단항 마이너스와 이항 마이너스가 함께 쓰이면 모호해진다. --34는 (- (- 3 4))로 읽어 1이 되고, (- (- 3) 4)로 읽어 -7이 되고, (- (- 34))로 읽어 34가 되기도 한다.

Jaap의 프로그램을 복원하는 문제가 아니다. 그가 출력한 문자열이 얼마나 모호한지를 알아내야 한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄이고, 길이가 1000 이하인 빈 문자열이 아닌 문자열 하나가 주어진다. 문자열에는 +와 -, 그리고 숫자 0부터 9까지만 들어 있다. 이 문자열은 Jaap의 프로그램이 출력한 결과다. 따라서 공백과 괄호를 뺀 전위 표기식으로 읽는 방법이 적어도 하나 있다. 입력이 끝날 때까지 주어지는 모든 테스트 케이스를 처리한다.

각 테스트 케이스마다 한 줄에 두 수를 출력한다. 입력 문자열을 서로 다르게 읽어서 얻을 수 있는 값 가운데 가장 작은 값과 가장 큰 값을 이 순서대로 공백 하나로 구분해 출력한다.