直接区间 dp 可以做到 \(O(n^3)\)，卡常可过，在此就不赘述了。
为了方便先把连续的数字缩成一段。我们考虑直接从前往后扫，扫的过程中 dp。设 \(f_{i, j}\) 为考虑了 \([1, i]\)，还有 \(j\) 个没配对的左括号的方案数。
但是我们发现我们不知道一个数字前要添加几个左括号，直接添加任意多个又会多算。
考虑我们把每个运算符的左式的括号全部去除，比如把 ((0)+(0))+((+(0))+(0)) 变成 0+(0)+((+0)+0)。发现处理后的串和原串一一对应！证明大概就是每次考虑右边管辖范围最大的一个运算符，它的左式一定是它左边的全部字符，然后递归两边还原即可。
所以我们现在就只用考虑在一个运算符后加一个左括号，或者在一个数字后加任意多个右括号。仍然用回之前的状态，\(f_{i, j}\) 为考虑了 \([1, i]\)，还有 \(j\) 个没配对的左括号的方案数。转移容易前缀和优化。
所以时间复杂度就是 \(O(n^2)\)。
code
// Problem: D. Unambiguous Arithmetic Expression
// Contest: Codeforces - Codeforces Beta Round 87 (Div. 1 Only)
// URL: https://codeforces.com/problemset/problem/115/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 2020;
const int mod = 1000003;
int n, f[maxn][maxn], m;
char s[maxn], t[maxn];
inline void upd(int &x, int y) {
x = (x + y < mod ? x + y : x + y - mod);
}
void solve() {
scanf("%s", s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; ++i) {
if (s[i] == '+' || s[i] == '-') {
t[++m] = '+';
} else if (s[i] == '*' || s[i] == '/') {
t[++m] = '*';
} else if (!m || t[m] != '0') {
t[++m] = '0';
}
}
if (t[1] == '*') {
puts("0");
return;
}
for (int i = 1; i < m; ++i) {
if (!isdigit(t[i]) && t[i + 1] == '*') {
puts("0");
return;
}
}
f[0][0] = 1;
for (int i = 1; i <= m; ++i) {
if (t[i] == '0') {
int s = 0;
for (int j = i; ~j; --j) {
upd(s, f[i - 1][j]);
f[i][j] = s;
}
} else {
for (int j = 1; j <= i; ++j) {
f[i][j] = f[i - 1][j - 1];
}
}
}
printf("%d\n", f[m][0]);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}