比赛 20121109 评测结果 AAAAAAAAAA
题目名称 表达式的值 最终得分 100
用户昵称 王者自由 运行时间 0.074 s
代码语言 C++ 内存使用 3.37 MiB
提交时间 2012-11-09 09:44:37
显示代码纯文本
#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;
}