精确算术 - 题目

令 $X$ 为所有有理数以及所有形如 $q\sqrt{r}$ 的数的集合，其中 $q$ 是非零有理数，$r$ 是大于 1 的整数。这里，$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 \cdot x_1)$ 压入栈中。
“div”：从栈顶依次弹出两个值 $x_1$ 和 $x_2$，然后将 $(x_2/x_1)$ 压入栈中。这里，$x_1$ 必须是 $X$ 中的非零值（不能来自 $X^*$）。
“sqrt”：从栈中弹出一个值 $x$，并将 $x$ 的平方根压入栈中。这里，$x$ 必须是非负有理数。
“disp”：从栈中弹出一个值 $x$，并将 $x$ 的字符串表示形式输出到显示器。表示规则在后文说明。
“stop”：终止计算。调用此指令时栈必须为空。

初始时，栈为空。执行每条指令时，栈中必须存在足够数量的值。此外，由于机器 $Y$ 的限制，当栈中已经存储了 256 个值时，不能再压入更多值。同时，压入栈中的值还存在以下限制：

对于有理数，其不可约分数形式的分子和分母的绝对值均不得超过 32 768。
对于 $X$ 中形如 $q\sqrt{r} = (a/b)\sqrt{r}$ 的任何元素，必须满足：$|a\sqrt{r}| \le 32 768$ 且 $|b| \le 32 768$。

对于 $X^*$ 中的任何元素，和中的每一项都必须满足上述条件。

机器 $Y$ 上值的字符串表示规则如下：

有理数表示为整数或分母大于 1 的不可约分数。
分数表示为 “num/den”。其中，num 是分子，den 是分母。负数前带有符号字符 “-”。
形如 $q\sqrt{r}$ 的数表示为 “rep*sqrt(r)”，但 $|q| = 1$ 的情况除外，此时若 $q = 1$ 则表示为 sqrt(r)，若 $q = -1$ 则表示为 -sqrt(r)。这里，rep 是 $q$ 的字符串表示。
对于两个或多个 $X$ 中元素的和，所有（非零）元素的字符串表示形式使用二元运算符 “+” 连接。在这种情况下，所有具有相同根号部分的项合并为一项，且各项必须按其根号部分的大小升序排列。为了应用此规则，所有有理数被视为伴随 $\sqrt{1}$。在每个二元运算符 “+” 前后恰好有一个空格字符。其他任何地方均不出现空格字符。

以下是有效字符串表示的一些示例： 0 1 -1/10 2sqrt(2) + 1/2sqrt(3) + -1/2*sqrt(5) 1/2 + sqrt(10) + -sqrt(30)

你的任务是编写一个模拟机器 $Y$ 的程序。

输入是一系列不超过 3000 条的指令。每行包含一条指令。你可以假设每条指令的调用都是合法的。指令 “stop” 只会出现一次，位于整个输入的末尾。

输出机器 $Y$ 将显示的所有字符串。每行输出一个字符串。

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)

QOJ.ac