[资料分享] 电路的稳定性

Problem Description
zzz有一个电路，电路上有n个元件。已知元件i损坏而断开的概率是Pi(i=1,2,…,n,0<=Pi<=1)。
请你帮zzz算出整个电路断路的概率。
元件的连接方式很简单，对电路的表示如下：
(1) 一个元件是最小的电路，用A表示元件1，B表示元件2，如此类推。
(2) k个电路组成的串联电路表示为电路1，电路2，……，电路k。
(3) k个电路组成的并联电路表示为(电路1)(电路2)……(电路k)。
Input
输入有多组测试数据，每组测试数据的第1行是一个整数n(1<=n<=26)，表示一共有多少个元件；
第2行是表示电路的字符串；
最后是n行，每行是一个实数Pi(i=1,2,…,n,0<=Pi<=1)，表示该元件断路的概率。
Output
对于每组测试数据输出一个实数表示整个电路断路的概率，精确到小数点后4位。
Sample Input
5
(A,B)((C)(D),E)
0.2
0.3
0.4
0.5
0.6
Sample Output
0.2992
//题解：并联电路短路的概率：x*y， 串联电路断路的概率:x+(1-x)*y.
//标程：
[cpp] view plain copy
#include  
#include  
#include  
#include  
using namespace std;  
string s, str;  
double p[30];  
int yx(char c)  
{  
    if(c=='+') return 1;  
    if(c=='*') return 2;  
    if(c=='(') return 0;  
}  
void compute(stack &s1, stack &s2)  
{  
    double x,y,ans;  
    char c;  
    y=s1.top(); s1.pop();  
    x=s1.top(); s1.pop();  
    c=s2.top(); s2.pop();  
    if(c=='+') ans=x+(1-x)*y;  
    if(c=='*') ans=x*y;  
    s1.push(ans);  
}  
int main()  
{  
//    freopen("a.txt","r",stdin);  
    int n;   
    while(scanf("%d\n",&n) != EOF)  
    {  
        str = "";  
        int i, flag=0;  
        double num;  
        stack s_int;  
        stack s_char;  
        cin >> s;  
        for(i = 0; i < n; i ++)  
            cin >> p[i];  
        str += '(';  
        for(i = 0; i < s.size(); i ++)  
        {  
            if(s[i] == ',')  { str += '+'; continue; }  
            str += s[i];  
            if(s[i] == ')' && s[i+1] == '(')    str += '*';     
        }  
        str += ')';  
        for(i = 0; i < str.size(); i ++)  
        {  
            if(str[i]>='A'&&str[i]<='Z') {num = p[str[i]-'A']; flag=1;}  
            else  
            {  
                if(flag) {s_int.push(num); num=0; flag=0;}  
                if(str[i]=='(') { s_char.push('('); continue;}  
                if(str[i]==')')  
                {  
                    while(s_char.top()!='(') compute(s_int,s_char);  
                    s_char.pop();  
                    continue;  
                }  
                if(s_char.empty()) s_char.push(str[i]);  
                else  
                {  
                    while(!s_char.empty()&&yx(s_char.top())>=yx(str[i]))   
                        compute(s_int,s_char);  
                    s_char.push(str[i]);  
                }  
            }  
        }  
        if(flag) {s_int.push(num); num=0; flag=0;}  
        while(!s_char.empty()) compute(s_int,s_char);  
        printf("%.4lf\n",s_int.top());  
        s_int.pop();     
    }  
    return 0;  
}