题解A100.表达式的值

#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;
}

链接描述