思路和题解一样,把序列转化成一个普通的带有 + - ()
的表达式求值,但是 RE,可能是栈出了问题,求助,谢谢大家
#include<iostream>
#include<cstdio>
#include<stack>
#include<string>
using namespace std;
int n,len;
double p[31];
string s;
stack<double> t;
stack<char> c;
inline double calc()
{
for(register int i=0;i<len;++i)
{
if(s[i]>='A'&&s[i]<='Z')
t.push(p[s[i]-'A'+1]);
if(s[i]=='(')
{
if(s[i-1]==')')
{
while(!c.empty()&&c.top()=='*')
{
double a=t.top();
t.pop();
double b=t.top();
t.pop();
t.push(a*b);
c.pop();
}
c.push('*');
}
c.push(s[i]);
}
if(s[i]==',')
{
while(!c.empty()&&c.top()!='(')
{
double a=t.top();
t.pop();
double b=t.top();
t.pop();
if(c.top()==',')
t.push(1-(1-a)*(1-b));
if(c.top()=='*')
t.push(a*b);
c.pop();
}
c.push(s[i]);
}
if(s[i]==')')
{
while(!c.empty()&&c.top()!='(')
{
double a=t.top();
t.pop();
double b=t.top();
t.pop();
if(c.top()==',')
t.push(1-(1-a)*(1-b));
if(c.top()=='*')
t.push(a*b);
c.pop();
}
if(!c.empty())
c.pop();
}
}
while(!c.empty())
{
double a=t.top();
t.pop();
double b=t.top();
t.pop();
if(c.top()=='*')
t.push(a*b);
if(c.top()=='+')
t.push(1-(1-a)*(1-b));
c.pop();
}
return t.top();
}
int main()
{
scanf("%d",&n);
cin>>s;
len=s.length();
for(register int i=1;i<=n;++i)
scanf("%lf",&p[i]);
printf("%.4f\n",calc());
return 0;
}