【正经题解】表达式的值

这道题可以用 $DP$ 求解，设 $f$ ( $s$ , $0$ )为 $s=0$ 的方案数， $f$ ( $s$ , $1$ )为 $s$ 为 $1$ 的方案数，则
$f$ ( $a+b$ , $0$ ) $=f$ ( $a$ , $0$ )* $f$ ( $b$ , $0$ )；
$f$ ( $a+b$ , $1$ ) $=f$ ( $a$ , $0$ )* $f$ ( $b$ , $1$ ) $+f$ ( $a$ , $1$ )* $f$ ( $b$ , $0$ ) $+f$ ( $a$ , $1$ )* $f$ ( $b$ , $1$ )；
$f$ ( $a$ * $b$ , $0$ ) $=f$ ( $a$ , $0$ )* $f$ ( $b$ , $0$ ) $+f$ ( $a$ , $1$ )* $f$ ( $b$ , $0$ ) $+f$ ( $a$ , $0$ )* $f$ ( $b$ , $1$ )；
$f$ ( $a$ * $b$ , $1$ ) $=f$ ( $a$ , $1$ )* $f$ ( $b$ , $1$ )。
接下来就是一个类似于树形 $DP$ 的过程了。在这里 $DP$ 的是表达式树。

#include <cstdio>
#include <iostream>
using namespace std;
struct dps
{
    int a[2];
};
const int key = 10007;
const dps empty = {{1, 1}};
int l, oslev = 1, fslev = 1;
dps fs[100005];
char os[100005], s[100003];
inline void calc(char op, dps &a, dps &b)
{
    if(op == '+')
    {
        a.a[1] = (a.a[1] * (b.a[0] + b.a[1]) + a.a[0] * b.a[1]) % key;
        a.a[0] = a.a[0] * b.a[0] % key;
    }
    else
    {
        a.a[0] = (a.a[0] * (b.a[0] + b.a[1]) + a.a[1] * b.a[0]) % key;
        a.a[1] = a.a[1] * b.a[1] % key;
    }
}
int main()
{
    scanf("%d%s", &l, &s);
    os[1] = '(';
    fs[1] = empty;
    s[l] = ')';

    for(int i = 0; i <= l; i++)
        if(s[i] == '(')
            os[++oslev] = '(';
        else if(s[i] == ')')
        {
            for(; os[oslev] != '('; --oslev, --fslev)
                calc(os[oslev], fs[fslev - 1], fs[fslev]);

            --oslev;
        }
        else
        {
            for(; (os[oslev] <= s[i]) && (os[oslev] != '('); --oslev, --fslev)
            {
                calc(os[oslev], fs[fslev - 1], fs[fslev]);
            }

            os[++oslev] = s[i];
            fs[++fslev] = empty;
        }

    printf("%d\n", fs[1].a[0]);
    return 0;
}