Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
119533 | 陈家宝 | 表达式的值 | C++ | 通过 | 100 | 2 MS | 660 KB | 985 | 2024-01-08 13:15:00 |
#include<bits/stdc++.h> using namespace std; struct dp{ int zero,one; }ans[150001]; int len,t = 1; const int mod = 10007; string str; stack<char> s; inline void dispose(char ch,dp &a,dp &b) { if(ch == '+'){ a.one = (a.one*(b.zero+b.one)+a.zero*b.one)%mod; a.zero = a.zero*b.zero%mod; } else{ a.zero = (a.zero*(b.zero+b.one)+a.one*b.zero)%mod; a.one = a.one*b.one%mod; } } int main() { cin >> len >> str; str += ')'; ans[1].zero = ans[1].one = 1; s.push('('); for(int i = 0;i <= len;i++){ if(str[i] == '(')s.push('('); else if(str[i] == ')'){ for(;s.top() != '(';s.pop(),t--) dispose(s.top(),ans[t-1],ans[t]); s.pop(); } else{ for(;s.top() <= str[i] && s.top() != '(';s.pop(),t--) dispose(s.top(),ans[t-1],ans[t]); s.push(str[i]); ans[++t].zero = 1; ans[t].one = 1; } } cout<<ans[1].zero; return 0; }