You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制： 1.0 秒

空间限制： 512 MB

题目描述

在本题当中，你需要设法描述一个表达式的计算过程。这个表达式可能含有：

• 四则运算（加 +、减 -、乘 *、除 /，不会出现负号，二元运算符，采用向左优先结合律）
• 括号（( 和 )）
• 乘方（^，二元运算符，采用向右优先结合律）
• 阶乘（!，一元运算符，采用向左优先结合律）
• 一些常量（常量前面不会添加负号）。

例如，(a!+b)*c^(d!+e)-(f!-gh-(i+j)) 就是一个可能出现的表达式。其中 a、b、c、d、e、f、gh、i、j 是常量。

向左优先结合律为：同运算符优先级的情况下，从左向右计算表达式结果。我们给出以下示例：

• $28+5-6+2=33-6+2=27+2=29$；
• $3!!=6!=720$。

向右优先结合律为：同运算符优先级的情况下，从右向左计算表达式结果。我们给出以下示例：

• $2^{3^2}=2^{9}=512$。

以上 3 个示例的表达式树图示分别为：

运算的优先级为：括号 > 阶乘 > 乘方 > 乘除法 > 加减法。注意：运算的优先级的大小不代表计算顺序的先后。

你不需要求出这个表达式的具体值，你只需要描述它的计算过程，即将这个表达式分解为若干次四则运算、乘方、阶乘，且每次运算或调用的操作数都是常量或之前的运算或调用的结果。

本题和《编译原理》的基础知识也有一定关联，但是只掌握《数据结构》相关知识点也可以做。

表达式的定义

一个常量可能是一个由 $1\sim 10$ 个小写英文字母组成的字符串。为了简化对于本题的理解，我们保证题目中的常量不会重复出现。

接下来我们使用递归的方式定义合法的表达式：

• 单独的一个常量是一个合法的表达式。

• 如果 [EXPR] 是一个合法的表达式，那么 ([EXPR]) 是一个合法的表达式，其值与 [EXPR] 相同。

• 如果 [EXPR] 是一个合法的表达式，那么 [EXPR]! 是一个合法的表达式，其值为 [EXPR] 计算阶乘的结果。

• 如果 [EXPR_0]、[EXPR_1]、$\cdots$、[EXPR_n] 是 $n+1$ 个上述三条规则定义的合法的表达式（$n$ 至少为 $1$），[OPR_1]、[OPR_2]、$\cdots$、[OPR_n] 为 $n$ 个乘方运算符，那么 [EXPR_0][OPR_1][EXPR_1][OPR_2]$\cdots$[OPR_n][EXPR_n] 是一个合法的表达式，其值为 [EXPR_0]、[EXPR_1]、$\cdots$、[EXPR_n] 依次进行 [OPR_n]、$\cdots$、[OPR_2]、[OPR_1] 运算的结果（请务必注意本条规则运算顺序与后两条运算规则的区别）。

• 如果 [EXPR_0]、[EXPR_1]、……、[EXPR_n] 是 $n+1$ 个上述四条规则定义的合法的表达式（$n$ 至少为 $1$），[OPR_1]、[OPR_2]、……、[OPR_n] 是 $n$ 个乘号或除号运算符，那么 [EXPR_0][OPR_1][EXPR_1][OPR_2]……[OPR_n][EXPR_n] 是一个合法的表达式，其值为将 [EXPR_0]、[EXPR_1]、$\cdots$、[EXPR_n] 依次进行 [OPR_1]、[OPR_2]、$\cdots$、[OPR_n] 运算的结果。

• 如果 [EXPR_0]、[EXPR_1]、$\cdots$、[EXPR_n] 是 $n+1$ 个上述五条规则定义的合法的表达式（$n$ 至少为 $1$），[OPR_1]、[OPR_2]、$\cdots$、[OPR_n] 是 $n$ 个加号或减号运算符，那么 [EXPR_0][OPR_1][EXPR_1][OPR_2]……[OPR_n][EXPR_n] 是一个合法的表达式，其值为将 [EXPR_0]、[EXPR_1]、$\cdots$、[EXPR_n] 依次进行 [OPR_1]、[OPR_2]、$\cdots$、[OPR_n] 运算的结果。

• 只有符合以上几条定义的表达式才是合法的。

此外，我们提供一种利用巴科斯范式（Backus-Naur form，BNF）给出的形式化定义：

<expr> ::= <term> {<'+'|'-'> <term>}
<term> ::= <factor3> {<'*'|'/'> <factor3>}
<factor3> ::= <factor2> { <'^'> <factor3>}
<factor2> ::= <factor> {'!'}
<factor> ::= <expr> | '(' <expr> ')' | <constant>
<constant> ::= <lowercase> | <constant> <lowercase>
<lowercase> ::= 'a' | 'b' | ... | 'z'

你可能需要了解的 BNF 基本语法如下：

• 尖括号 <> 内是必选项：必须出现 1 次；
• 方括号 [] 内是可选项：可以出现 0 或 1 次；
• 大括号 {} 内：可以出现 0 或无数次；
• 竖线 |：其左右两侧的内容任选一项组成；
• 定义符 ::=：表示左侧的内容由右侧组成。

容易看到，这样定义的每个合法的表达式都有唯一一种解读方式，即不会引起歧义。

此外，在本题当中你不需要考虑计算结果是否合法（例：阶乘运算的操作数是否为整数、除法运算的第二个操作数是否不为 $0$），只需要考虑表达式本身的合法性即可。我们保证输入的表达式都是合法的。

如果上面的递归或者 BNF 定义你都看不懂也没关系，你只要知道合法表达式就是符合一般常识，且开头没有负号的表达式。

计算顺序的规定

上述规定确定了一个表达式的值，接下来我们确定一个表达式的求值顺序。我们用与定义类似的方式规定这个顺序：

• 对于单独的一个常量，不需要计算。

• 对于 ([EXPR]) ，只需计算 [EXPR] 。

• 对于 [EXPR][OPR_1]……[OPR_n]（其中 [OPR_1]、[OPR_2]、$\cdots$、[OPR_n] 全为阶乘），先用 [EXPR] 调用 [OPR_1] 得出中间结果，再用上述中间结果调用 [OPR_2] 得到下一个中间结果……直到计算完毕。

• 对于 [EXPR_0][OPR_1][EXPR_1][OPR_2]……[OPR_n][EXPR_n]（其中 [OPR_1]、[OPR_2]、$\cdots$、[OPR_n] 全为乘方），先依次计算 [EXPR_0]、[EXPR_1]、$\cdots$、[EXPR_n]，接下来用 [EXPR_n] 和 [EXPR_{n-1}] 调用 [OPR_n] 得出中间结果，再用上述中间结果和 [EXPR_{n-2}] 调用 [OPR_{n-1}] 得到下一个中间结果……直到计算完毕。请注意该条规则的计算顺序与后两条规则计算顺序的区别。

• 对于 [EXPR_0][OPR_1][EXPR_1][OPR_2]……[OPR_n][EXPR_n] （其中 [OPR_1]、[OPR_2]、……、[OPR_n] 全为乘除或全为加减），先计算 [EXPR_0] ，再计算 [EXPR_1] ，再调用 [OPR_1] 得出中间结果，再计算 [EXPR_2] ，再用上述中间结果和 [EXPR_2] 的结果调用 [OPR_2] ……直到计算完毕。

可以看出，上述运算顺序均与我们日常使用的顺序相同。对于任何一个合法的表达式，其计算顺序一定是唯一的。

输入格式

从标准输入读入数据。

输入文件只有一行，以换行符结束，只包含一个需要处理的表达式。

输出格式

输出到标准输出。

按计算顺序输出每一次的运算符与函数调用。每次调用的参数只能是常量或之前某一次的运算结果，其中运算结果我们用从小到大的正整数依次表示。

即：我们用 $1\sim 10$ 个英文字母（与输入中的相同）表示一个常量，用一个正整数表示之前某一次的运算结果，设第 $i$ 次的调用产生的结果为 $i$。

以下用 [VALUE] 表示一个参数，[OPR] 表示一个运算符。

如果是二元运算符，设这次要计算的是 [VALUE_1][OPR][VALUE_2]，则你需要输出一行 [OPR][空格][VALUE_1][空格][VALUE_2]。

如果是一元运算符，设这次要计算的是 [VALUE][OPR]，则你需要输出一行 [OPR][空格][VALUE]。本题当中的一元运算符只有阶乘。

不难得到，本题的运算顺序一定是唯一的。

(a+b+c)+d+e+f+(g+h+i)

+ a b
+ 1 c
+ 2 d
+ 3 e
+ 4 f
+ g h
+ 6 i
+ 5 7

样例 1 解释

本样例只涉及加法运算和括号，因此先计算完 (a+b+c)（表达式 2）之后，继续连带计算 (a+b+c)+d（表达式 2）、(a+b+c)+d+e（表达式 4）、(a+b+c)+d+e+f（表达式 5），而由于括号优先级更大，因此需要先计算完 (g+h+i)（表达式 7），再计算最终结果（表达式 5 + 表达式 7）。

a+b+c+d+e*f*g*h*i*(j-k-l-m-n)

+ a b
+ 1 c
+ 2 d
* e f
* 4 g
* 5 h
* 6 i
- j k
- 8 l
- 9 m
- 10 n
* 7 11
+ 3 12

样例 2 解释

本样例包括四则运算和括号，在计算完表达式 3 之后，要先从左往右计算连乘的部分。

((a!!)^(b!*c+d)^(e-f*g))!

! a
! 1
! b
* 3 c
+ 4 d
* f g
- e 6
^ 5 7
^ 2 8
! 9

样例 3 解释

本样例涉及到阶乘和乘方的连算，注意到两者分别满足向左优先结合律和向右优先结合律，这一点体现在了 a!! 以及 (表达式 2)^(表达式 5)^(表达式 7) 的运算过程当中。下放对于样例 3 输出的注释则表达了每个具体计算的子表达式。

! a            // 1  a!
! 1            // 2  a!!
! b            // 3  b!
* 3 c          // 4  b!*c
+ 4 d          // 5  b!*c+d
* f g          // 6  f*g
- e 6          // 7  e-f*g
^ 5 7          // 8  (b!*c+d)^(e-f*g)
^ 2 8          // 9  (a!!)^(b!*c+d)^(e-f*g)
! 9            // 10 ((a!!)^(b!*c+d)^(e-f*g))!

关于如何表达向右优先结合律，详见邓俊辉《数据结构》习题 [4-10]。

(a!+b)*c^(d!+e)-(f!-gh-(i+j))

! a
+ 1 b
! d
+ 3 e
^ c 4
* 2 5
! f
- 7 gh
+ i j
- 8 9
- 6 10

样例 4 解释

本样例同邓俊辉《数据结构》习题 [4-9]。

子任务

对于所有数据，保证：

• 表达式的长度不超过 $2.1\times 10^6$，操作数个数不超过 $1.5\times 10^5$；
• 不会出现任何空格等多余字符，最后以换行符结尾；
• 表达式在上述定义的规则下是合法的；
• 表达式中的常量长度为 $1\sim 10$，只由小写字符组成，且不会出现相同的常量；
• 表达式含加/减/乘/除/乘方/阶乘运算符当中的至少一种。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

• 子任务 1（30 分）：包含常量、加减号、括号；
• 子任务 2（30 分）：包含常量、四则运算符、括号；
• 子任务 3（30 分）：包含常量、四则运算符、乘方运算符、阶乘运算符，操作数个数不超过 $3000$，表达式长度不超过 $4\times 10^4$；
• 子任务 4（10 分）：包含常量、四则运算符、乘方运算符、阶乘运算符。

提示

Chap 04 栈与队列，延迟缓冲-表达式求值

Chap 05 二叉树，二叉树的后序遍历

本题前面的定义之所以这么复杂，主要是为了严谨定义。

说白了，本题就是让你求出对应的表达式树结构（需要对教材代码进行改造），并对表达式树进行后序遍历。每一行输出的就是当前运算符所代表的节点，以及其左右子节点参与运算的常量或表达式。实际上输出的运算顺序也是将中缀表达式转为逆波兰表达式之后的运算顺序。

由于本题只包含一元和二元运算符，因此表达式树一定是一个二叉树。而一元运算符的子树只有一个，放在左子树和右子树都不影响后序遍历顺序的唯一性，自由操作即可。

关于向左优先结合律与向右优先结合律，本质上就是在运算优先级相同的连续运算下，将运算过程中所产生的中间结果放在左子树或者右子树，而由此产生的调用运算顺序均满足二叉树的后序遍历形式。

需要注意本题的数据范围，我们需要一个线性时间复杂度的做法来完成表达式的解析。在《数据结构》的知识点内，只有维护栈+运算符优先级能够做到这个复杂度。

当然，注意到子任务 3 的长度限制，我们暴力地利用递归定义进行解析也是能拿到部分分的，而且这个过程也是需要栈进行括号匹配的。

此外，使用《编译原理》的相关知识点，利用题目描述中的 BNF 进行递归下降解析也能通过。

来源

本题改编自[清华预推免机试 2016] 表达式求值。