记得 11 年的时候，觉得这道题爆难，根本无从下手。三年后再次回顾，终于 AC 了，就当是对表达式求值和动态规划的复习吧。

题目：Link

// Accepted.
#include <iostream>
#define Mod 10007
using namespace std;

typedef struct {
    long long v0;  //当前值为 0 的个数
    long long v1;  //当前值为 1 的个数
    char ch;  //当前字符
} vertex;

vertex f[100000];

void merge_sum(int p) {
    int w0 = f[p-1].v0 * f[p].v0;
    int w1 = f[p-1].v0*f[p].v1+f[p-1].v1*f[p].v0+f[p-1].v1*f[p].v1;
    f[p-1].v0 = w0 % Mod;
    f[p-1].v1 = w1 % Mod;
}

inline void merge_product(int p)  //处理当前的值和前一个值取'*'的操作
{
       int w0=f[p-1].v0*f[p].v0+f[p-1].v0*f[p].v1+f[p-1].v1*f[p].v0;
       int w1=f[p-1].v1*f[p].v1;
       f[p-1].v0=w0%Mod;
       f[p-1].v1=w1%Mod;
}

int main()
{
    int n;
    cin>>n;
    f[0].v0=f[0].v1=1;
    while (n--)
    {
          now++;   //新建一个空位读入新符号
          cin>>f[now].ch;
          f[now].v0=f[now].v1=1;  //初始化当前符号的前面的值 (虽然')'除外，但也不影响)
          if (f[now].ch=='+')
          {
             if (f[now-1].ch=='*') //处理'*'
             {
                now--;
                merge_product(now);
                f[now]=f[now+1];
             }
             if (f[now-1].ch=='+') //处理'+'
             {
                now--;
                merge_sum(now);
                f[now]=f[now+1];
             }
          }
          if (f[now].ch=='*')
           if (f[now-1].ch=='*') //处理'*'
           {
              now--;
              merge_product(now);
              f[now]=f[now+1];
           }
          if (f[now].ch==')') //处理')'(比较麻烦)
          {
             now--;
             if (f[now].ch=='*')
             {
                merge_product(now);
                now--;
             }
             if (f[now].ch=='+')
             {
                merge_sum(now);
                now--;
             }
             now--;
             f[now].v0=f[now+1].v0;
             f[now].v1=f[now+1].v1;
             if (f[now].ch=='*')
             {
                merge_product(now);
                now--;
             }
          }
    }
    if (f[now].ch=='*')  //处理完了以后，可能还有残留的'*'和'+'
    {
       merge_product(now);
       now--;
    }
    if (f[now].ch=='+')
    {
       merge_sum(now);
       now--;
    }
    cout<<f[0].v0;
    return 0;
}

作者：hsfzxjy
链接：
许可：CC BY-NC-ND 4.0.
著作权归作者所有。本文不允许被用作商业用途，非商业转载请注明出处。