#CW30. 算式还原(expression)

算式还原(expression)

题目描述

小 Z 使用以下规则书写完整括号算式:

  1. 任意非空数字串都是合法算式,允许前导零;
  2. 若 X,YX,Y 是合法算式,则 (X)+(Y)、(X)-(Y)、(X)*(Y)、(X)/(Y) 都是合法算式;
  3. 若 XX 是合法算式,则 +(X) 和 -(X) 都是合法算式。

由上述规则生成的带括号字符串不同,就视为不同算式。这里不计算算式的数值,因此除数是否为零不会影响合法性。

现在给定一个删除了全部括号的字符串。求有多少个不同的合法算式在删除全部括号后恰好得到该字符串。答案对 10000031000003 取模。

输入格式

输入一行非空字符串 ss。字符串只含数字以及 +、-、*、/,不含空格。

输出格式

输出一个整数,表示答案对 10000031000003 的余数。

样例 1 输入

1++2+3

样例 1 输出

3

样例 1 解释

样例 1 对应以下三个合法算式:

  1. ((1)+(+(2)))+(3)
  2. (1)+((+(2))+(3))
  3. (1)+(+((2)+(3)))

样例 2 输入

5//4

样例 2 输出

0

样例 2 解释

两个 / 之间没有数字,第二个 / 又不能作为一元运算符,因此不存在合法算式。

数据范围

对于所有测试数据,保证 1≤∣s∣≤20001 \le |s| \le 2000。

数据类别 分值 测试点 附加条件
A 10 1∼21\sim 2 $
B 15 3∼53\sim 5
C 20 6∼96\sim 9 ss 以数字开头和结尾,且不存在相邻的两个运算符
D 25 10∼1410\sim 14 ss 中极大连续数字子串的数量不超过 100100
E 30 15∼2015\sim 20 无额外限制