#CW30. 算式还原(expression)
算式还原(expression)
题目描述
小 Z 使用以下规则书写完整括号算式:
- 任意非空数字串都是合法算式,允许前导零;
- 若 是合法算式,则
(X)+(Y)、(X)-(Y)、(X)*(Y)、(X)/(Y)都是合法算式; - 若 是合法算式,则
+(X)和-(X)都是合法算式。
由上述规则生成的带括号字符串不同,就视为不同算式。这里不计算算式的数值,因此除数是否为零不会影响合法性。
现在给定一个删除了全部括号的字符串。求有多少个不同的合法算式在删除全部括号后恰好得到该字符串。答案对 取模。
输入格式
输入一行非空字符串 。字符串只含数字以及 +、-、*、/,不含空格。
输出格式
输出一个整数,表示答案对 的余数。
样例 1 输入
1++2+3
样例 1 输出
3
样例 1 解释
样例 1 对应以下三个合法算式:
((1)+(+(2)))+(3)(1)+((+(2))+(3))(1)+(+((2)+(3)))
样例 2 输入
5//4
样例 2 输出
0
样例 2 解释
两个 / 之间没有数字,第二个 / 又不能作为一元运算符,因此不存在合法算式。
数据范围
对于所有测试数据,保证 。
| 数据类别 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| A | 10 | $ | |
| B | 15 | ||
| C | 20 | 以数字开头和结尾,且不存在相邻的两个运算符 | |
| D | 25 | 中极大连续数字子串的数量不超过 | |
| E | 30 | 无额外限制 |