정확 산술

시간 제한8초메모리 제한512 MB

요약

a/b와 c/d 곱하기 sqrt(r) 꼴의 수를 다루는 스택 계산기를 시뮬레이션하고, 정확한 연산과 정규화된 출력 형식을 유지한다.

난이도: 어려움10점 중 9점
유형: 구현, 시뮬레이션, 수학, 정수론
정답자: 아직 제출이 없습니다

문제

모든 유리수와, 0이 아닌 유리수 $q$ 와 1보다 큰 정수 $r$ 에 대해 $q\sqrt{r}$ 꼴로 표현되는 수 전체의 집합을 $X$ 라고 하자. 여기서 $r$ 은 1을 제외한 제곱수를 약수로 가져서는 안 된다. 또한 $X$ 의 원소 하나 이상의 합으로 표현될 수 있는 모든 수의 집합을 $X^*$ 라고 하자.

기계 $Y$ 는 $X^*$ 의 값들을 다루는 스택 기반 계산기이며, 아래 표에 나온 명령어를 가진다.


`push` n	피연산자로 주어진 정수를 스택에 넣는다.
`add`	스택 맨 위에서 두 값 $x_1$ 과 $x_2$ 를 이 순서대로 꺼낸 뒤, ( $x_2$ + $x_1$ )을 스택에 넣는다.
`sub`	스택 맨 위에서 두 값 $x_1$ 과 $x_2$ 를 이 순서대로 꺼낸 뒤, ( $x_2$ - $x_1$ )을 스택에 넣는다.
`mul`	스택 맨 위에서 두 값 $x_1$ 과 $x_2$ 를 이 순서대로 꺼낸 뒤, ( $x_2$ × $x_1$ )을 스택에 넣는다.
`div`	스택 맨 위에서 두 값 $x_1$ 과 $x_2$ 를 이 순서대로 꺼낸 뒤, ( $x_2$ ÷ $x_1$ )을 스택에 넣는다. $x_1$ 은 $X$ 의 0이 아닌 값이어야 한다( $X^*$ 가 아니다).
`sqrt`	스택에서 값 $x$ 하나를 꺼내고 $x$ 의 제곱근을 스택에 넣는다. $x$ 는 음이 아닌 유리수여야 한다.
`disp`	스택에서 값 $x$ 하나를 꺼내고, 그 값 $x$ 의 문자열 표현을 화면에 출력한다. 표현 규칙은 아래에 나온다.
`stop`	계산을 끝낸다. 이 명령이 호출될 때 스택은 비어 있어야 한다.

표 1: 기계 Y의 명령어 집합

모든 명령을 실행할 때 스택에는 값이 충분히 있어야 한다. 또한 기계 Y의 한계로 인해 스택에 이미 256개의 값이 저장되어 있으면 더 이상 값을 넣을 수 없다. 스택에 넣는 값에는 다음과 같은 제약도 있다.

유리수의 경우, 기약분수 형태에서 분자와 분모의 절댓값이 각각 32,768을 넘을 수 없다.
$X$ 의 원소 중 $q\sqrt{r}$ = ( $a$ / $b$ ) $\sqrt{r}$ 꼴인 수에 대해, | $a\sqrt{r}$ | ≤ 32,768이고 | $b$ | ≤ 32,768이다.
$X^*$ 의 원소에 대해, 합을 이루는 각 항이 위 조건을 만족해야 한다.

기계 Y에서 값의 문자열 표현 규칙은 다음과 같다.

유리수는 정수 또는 분모가 1보다 큰 기약분수로 표현한다. 분수는 "<분자>/<분모>"로 표현한다. 음수인 경우 앞에 부호 기호 -를 붙인다.
$q\sqrt{r}$ 꼴의 수는 $q$ = ±1인 경우를 제외하고 "<q의 문자열 표현>*sqrt(r)"로 표현한다. $q$ = 1이면 "sqrt(r)", $q$ = -1이면 "-sqrt(r)"로 표현한다.
$X$ 의 원소 두 개 이상의 합에 대해서는 (0이 아닌) 모든 원소의 문자열 표현을 이항 연산자 +로 연결한다. 이때 근호 안의 수가 같은 항은 모두 하나로 합쳐지며, 항들은 근호 성분이 커지는 순서대로 나타나야 한다. 이 규칙에서 모든 유리수는 √1을 동반하는 것으로 본다.
이항 연산자 +의 앞뒤에는 정확히 공백 문자가 하나씩 있다. 다른 곳에는 공백 문자가 나타나지 않는다.

다음은 올바른 문자열 표현의 몇 가지 예이다.

0
1
-1/10
2*sqrt(2) + 1/2*sqrt(3) + -1/2*sqrt(5)
1/2 + sqrt(10) + -sqrt(30)

여러분의 과제는 기계 Y를 시뮬레이션하는 프로그램을 작성하는 것이다.

입력

입력은 명령어의 나열이다. 각 줄에는 명령어가 하나씩 들어 있다. 모든 명령어는 올바른 방식으로 호출된다고 가정할 수 있다. stop 명령은 전체 입력의 맨 끝에 한 번만 나타난다.

출력

기계 Y가 화면에 출력할 문자열을 출력한다. 각 문자열을 한 줄에 하나씩 출력한다.

예제1

예제 1

입력

push 1
push 2
sqrt
div
push 1
push 3
sqrt
div
add
disp
push 8
sqrt
push 3
push 2
sqrt
mul
add
disp
stop

예상 출력

1/2*sqrt(2) + 1/3*sqrt(3)
5*sqrt(2)