记录编号	49808	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]表达式的值	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2012-11-09 13:03:27	内存使用	0.36 MiB

#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
const int L = 100000 + 10, M = 10007;
unsigned int l, a[2], b[2], r[2];
char exp[L], c;
stack<int> s[2], o;
inline bool equal(int i) {
    return o.top() == '(' && exp[i] == ')';
}
inline bool lower(int i) {
    return (o.top() == '(' && exp[i] != ')')
        || (o.top() == '*' && exp[i] == '(')
        || (o.top() == '+' && (exp[i] == '(' || exp[i] == '*'));
}
int main() {
    freopen("exp.in", "r", stdin);
    freopen("exp.out", "w", stdout);
    scanf("%d\n", &l);
    scanf("%s\n", exp);
    exp[l++] = ')'; o.push('(');
    s[0].push(1), s[1].push(1);
    for(int i=0; i<l; ) {
        if(equal(i)) {
            o.pop();
            i++;
        } else if(lower(i)) {
            o.push(exp[i]);
            if(exp[i] != '(') s[0].push(1), s[1].push(1);
            i++;
        } else {
            for(int j=0; j<2; j++) {
                a[j] = s[j].top(), s[j].pop();
                b[j] = s[j].top(), s[j].pop();
            } c = o.top(), o.pop();
            if(c == '+') {
                r[0] = (a[0] * b[0]) % M;
                r[1] = (a[0] * b[1] % M + a[1] * b[0] % M + a[1] * b[1] % M) % M;
            } else if(c == '*') {
                r[0] = (a[0] * b[1] % M + a[1] * b[0] % M + a[0] * b[0] % M) % M;
                r[1] = (a[1] * b[1]) % M;
            } s[0].push(r[0]), s[1].push(r[1]);
        }
    } printf("%d\n", s[0].top());
    return 0;
}