Problem K. 后缀表示法

时间限制：1s

空间限制：256MB

题目描述

  xv1r 高中时购入了一台带有 CAS 的计算器, 这台计算器同时也支持对后缀表达式求值. 经过长期使用, xv1r 认为后缀表示法比中缀表示法在许多方面更高效, 因此他希望制作一个计算机程序来对后缀表达式求值.

  然而, xv1r 的程序设计能力有限, 无法完成如此挑战. 请你为 xv1r 设计一个程序, 完成对后缀表达式求值的任务.

输入描述

  输入的第 $1$ 行是一个正整数 $n$, 代表数值和运算符的总个数.

  第 $2$ 行是 $1$ 行 $n$ 个 Token, 每个 Token 代表一个非负数值 $a$ 或一个运算符 $op$, 不同 Token 间由空格分隔, 模拟 xv1r 使用计算器时的输入.

输出描述

  输出 $1$ 行 $1$ 个数, 即后缀表达式求值的结果, 保留四位小数.

输入输出样例

输入 #1

1
2147483647

输出 #1

2147483647.0000

输入 #2

7
9 5 2 + - 3 *

输出 #2

6.0000

输入 #3

5
2 3 / 3 *

输出 #3

1.9998

说明/提示

输入输出样例解释

对于输入输出 #3, 首先计算 $2\div3$ 并舍去无法除尽时末尾的余数, 得到 $0.6666$, 然后计算 $0.6666\times3$, 得到 $1.9998$ , 即为最终结果.

数据范围与约定

  对于 $40\%$ 的数据, 保证 $n\leq10^3$, $a<2^{31}$, $a\in\N$, $op\in\left\{+,-,*\right\}$.

  对于 $80\%$ 的数据, 保证 $n\leq10^3$, $a<10^{97}$, $a\in\N$, $op\in\left\{+,-,*\right\}$.

  对于 $100\%$ 的数据, 保证 $n\leq10^3$, $a<10^{97}$, $a\cdot10^4\in\N$, $op\in\left\{+,-,*,/\right\}$.

  额外地, 我们约定:

1. xv1r 输入的后缀表达式可以被求值.
2. 按照顺序计算时, 每步的步骤结果均不会超出对应 $a$ 的数据范围.
3. 每次进行除法运算时, 舍去无法除尽时末尾的余数, 而不是四舍五入.

背景知识

  后缀表示法是波兰逻辑学家 Jan Łukasiewicz 于 1924 年提出的一种表达式的表示方法. 我们常用的表示法是中缀表示法, 其遵循“先乘除, 后加减, 括号优先”的运算顺序. 许多编译器在编译过程中, 将运算顺序复杂的中缀表达式翻译为从左到右的, 不需要括号额外说明运算顺序的, 易于计算机处理的后缀表达式, 以便于求值等操作.

  一个中缀表达式 $E$ 的后缀表示可以按照下面的方式进行归纳定义:

1. 如果 $E$ 是一个变量或常量, 则 $E$ 的后缀表示是 $E$ 本身.
2. 如果 $E$ 是一个形如 $E_1\ \mathbf{op}\ E_2$ 的表达式, 其中 $\mathbf{op}$ 是一个二目运算符, 那么 $E$ 的后缀表示是 $E'_1\ E'_2\ \mathbf{op}$, 这里 $E'_1$ 和 $E'_2$ 分别是 $E_1$ 和 $E_2$ 的后缀表示.
3. 如果 $E$ 是一个形如 $(E_1)$ 的被括号括起来的表达式, 则 $E$ 的后缀表示就是 $E_1$ 的后缀表示.

(例 1) $(9-5)+2$ 的后缀表示是 $9\ 5-2\ +$.   也就是说, 由规则 1 可知, $9$, $5$ 和 $2$ 的翻译结果就是这些常量本身. 然后, 根据规则 2, $9-5$ 的翻译结果是 $9\ 5\ -$. 由规则 3 可知, $(9-5)$ 的翻译结果与此相同. 翻译完带括号的子表达式后, 我们可以将规则 2 应用于整个表达式, $(9-5)$ 就是 $E_1$, $2$ 为 $E_2$, 由此得到结果 $9\ 5-2\ +$.

(例 2) $9-(5+2)$ 的后缀表达式是 $9\ 5\ 2+-$.   也就是说, $5+2$ 首先被翻译成 $5\ 2\ +$, 然后这个表达式又成为减号的第二个运算分量.

  运算符的位置和它的运算分量个数使得后缀表达式只有一种解码方式, 所以在后缀表示中不需要括号. 处理后缀表达式的“技巧”就是从头开始不断扫描后缀串, 直到发现一个运算符为止. 然后向左找出适当数目的运算分量, 并将这个运算符和它的运算分量组合在一起. 计算出这个运算符作用于这些运算分量上后得到的结果, 并用这个结果替换原来的运算分量和运算符. 然后继续这个过程, 向右搜寻另一个运算符.

(例 3) 考虑后缀表达式 $9\ 5\ 2+-\ 3\ \times$.   从左边开始扫描, 我们首先遇到加号. 向加号的左边看, 我们找到运算分量 $5$ 和 $2$. 用它们的和 $7$ 替换原来的 $5\ 2\ +$, 这样我们得到串 $9\ 7-3\ \times$.   现在最左边的运算符是减号, 它的运算分量是 $9$ 和 $7$. 将这些符号替换为它们的差, 得到 $2\ 3\ \times$.   最后, 将乘号应用在 $2$ 和 $3$ 上, 得到结果 $6$.