Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
119533 陈家宝 表达式的值 C++ 通过 100 2 MS 660 KB 985 2024-01-08 13:15:00

Tests(10/10):


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


测评信息: