电路稳定性
时间： 3ms 内存：64M
描述：
Heinz有一个电路，电路上有n个元件。已知元件i损坏而断开的概率是Pi（i=1，2，...，n，0≤pi≤1)。请你帮Heinz算出整个电路断路的概率。
元件的连接方式很简单，对电路的表示如下：
（1）一个元件是最小的电路，用A表示元件1，B表示元件2，如此类推。
（2）k个电路组成的串联电路表示为电路1，电路2，......，电路k。注串联电路用“，”号隔开。
（3）k个电路组成的并联电路表示为（电路1）（电路2）......(电路k)。注并联电路用“（ ）”标示。
对于两个电阻，如果它们断开的概率是P(i)和P(j)时,有：
（1）如果它们是并联电路，则断开的概率是P(i)*P(j)。
（2）如果它们是串联电路，则断开的概率是P(i)+(1-P(i))*P(j)。
输入：
第1行是一个整数n（2≤n≤26），表示一共有多少个元件；
第2行是表示电路的字符串；
最后是n行，每行是一个实数Pi（i=1，2，...，n，0≤pi≤1），表示该元件断路的概率。
输出：
输出一个实数，表示整个电路断路的概率，精确到小数点后4位。
示例输入：
5
(A,B)((C)(D),E)
0.2
0.3
0.4
0.5
0.6示例输出：
0.2992
提示：
参考答案（内存最优[1272]）：
#include<iostream>
#include<string>
#include<cstdio>
#include<stack>
using namespace std;
int n;
double p[30];
string s;
stack<char> sign;
stack<double> data;
void cal()
{
double a,b,temp;
b=data.top();
data.pop();
a=data.top();
data.pop();
switch(sign.top())
{
case ',':
temp=a+b*(1-a);
break;
case '*':
temp=a*b;
break;
}
sign.pop();
data.push(temp);
}
void work()
{
for(int i=0;i<s.size();i++)
{
if(s[i]>='A'&&s[i]<='Z')data.push(p[s[i]-'A']);
else if(s[i]==',')
{
while(!sign.empty()&&sign.top()!='(')cal();
sign.push(s[i]);
}
else if(s[i]=='(')
{
if(i!=0&&s[i-1]==')')sign.push('*');
sign.push(s[i]);
}
else if(s[i]==')')
{
if(sign.top()=='(')sign.pop();
else
{
while(sign.top()!='(') cal();
sign.pop();
}
}
}
while(!sign.empty())cal();
printf("%.4lf\n",data.top());
data.pop();
}
int main()
{
scanf("%d",&n);
cin>>s;
for(int i=0;i<n;i++)scanf("%lf",&p[i]);
work();
return 0;
}参考答案（时间最优[0]）：
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <iomanip>
using namespace std;
#ifndef _CALCULATOR_H
#define _CALCULATOR_H
class Calculator
{
public:
string trans_to_postfix_expression_to_s(string);
double calculate_from_postfix_expression();
bool bracket_check(string);
bool operator_check(string);
private:
vector<string> ans_vector_post;
string post_string;
};
inline int prior(char op)
{
if (op == '+' || op == '-')
{
return 1;
}
else if (op == '*' || op == '/' || op == '%')
{
return 2;
}
else
{
return 0;
}
}
double string_to_double(string in)
{
char s[50];
for (int i = 0; i < 50; i++)
{
s[i] = '\0';
}
for (int i = 0; i < (int)in.size(); i++)
{
s[i] = in[i];
}
double ans;
sscanf(s, "%lf", &ans);
return ans;
}
string erase_blank(string s)
{
for (int i = 0; i < (int)s.size();)
{
if (s[i] == ' ') s.erase(i, 1);
else i++;
}
return s;
}
string dealWithNegative(string s)
{
for (int i = 0; i < (int)s.size() - 1; i++)
{
if (s[i] == '-' && s[i + 1] == '(') s.insert(i + 1, "1*");
}
return s;
}
bool Calculator::bracket_check(string in)
{
stack<char> st_bracket;
for (int i = 0; i <(int) in.size(); i++)
{
if (in[i] == '(' || in[i] == ')')
{
if (st_bracket.empty())
{
st_bracket.push(in[i]);
}
else
{
if (st_bracket.top() == '(' && in[i] == ')')
{
st_bracket.pop();
}
else
{
st_bracket.push(in[i]);
}
}
}
}
if (st_bracket.empty())
{
return 1;
}
else
{
return 0;
}
}
inline bool isLegal(char c)
{
return ('0' <= c && c <= '9') || c == '.' || c == '+' || c =='-' || c == '*' || c == '/' || c == '(' || c == ')' || c == ' ';
}
inline bool isOperator(char c)
{
return c == '.' || c == '+' || c =='-' || c == '*' || c == '/';
}
bool Calculator::operator_check(string in)
{
for (int i = 0; i <(int) in.size(); i++)
{
if (!isLegal(in[i])) return false;
if (i > 0 && isOperator(in[i]) && isOperator(in[i - 1])) return false;
if (i > 0 && in[i] == '(' && in[i - 1] == ')') return false;
}
return true;
}
string Calculator::trans_to_postfix_expression_to_s(string in)
{
stack<char> op;
ans_vector_post.clear();
bool nextIsNega = false;
for (int i = 0; i < (int)in.size();)
{
char c = in[i];
if ((i > 0 && (in[i - 1] == '+' || in[i - 1] == '-' || in[i - 1] == '*' || in[i - 1] == '/' || in[i - 1] == '(') && in[i] == '-') || (i == 0 && in[i] == '-'))
{
nextIsNega = true;
i++;
continue;
}
if (('0' <= c && c <= '9') || c == '.')
{
string num;
int j;
for (j = i; j <(int) in.size() && (('0' <= in[j] && in[j] <= '9') || in[j] == '.'); j++)
{
num.push_back(in[j]);
}
if (nextIsNega)
{
num = "-" + num;
nextIsNega = false;
}
ans_vector_post.push_back(num);
i = j;
}
else
{
if (c == '(')
{
op.push('(');
}
else
{
if (c == ')')
{
while (op.top() != '(')
{
string temp;
temp.push_back(op.top());
ans_vector_post.push_back(temp);
op.pop();
}
op.pop();
}
else
{
if (op.empty())
{
op.push(c);
}
else {
if (prior(c) > prior(op.top()))
{
op.push(c);
}
else
{
while (!op.empty() && prior(c) <= prior(op.top()))
{
string temp;
temp.push_back(op.top());
ans_vector_post.push_back(temp);
op.pop();
}
op.push(c);
}
}
}
}
i++;
}
}
while (!op.empty())
{
string temp;
temp.push_back(op.top());
ans_vector_post.push_back(temp);
op.pop();
}
post_string.clear(); // 构造string并返回
for (int i = 0; i <(int) ans_vector_post.size(); i++)
{
post_string += ans_vector_post[i];
}
return post_string;
}
double Calculator::calculate_from_postfix_expression()
{
stack<double> ans_post;
for (int i = 0; i <(int) ans_vector_post.size(); i++)
{
double x, y;
if (('0' <= ans_vector_post[i][0] && ans_vector_post[i][0] <= '9') || (ans_vector_post[i][0] == '-' && '0' <= ans_vector_post[i][1] && ans_vector_post[i][1] <= '9'))
{
ans_post.push(string_to_double(ans_vector_post[i]));
}
else
{
y = ans_post.top();
ans_post.pop();
x = ans_post.top();
ans_post.pop();
if (ans_vector_post[i][0] == '+')
{
ans_post.push(1.0 - (x * (1 - y) + (1 - x) * y + (1 - x) * (1 - y)));
}
else if (ans_vector_post[i][0] == '-')
{
ans_post.push(x - y);
}
else if (ans_vector_post[i][0] == '*')
{
ans_post.push(1.0 - ((1 - x) * (1 - y)));
}
else if (ans_vector_post[i][0] == '/')
{
ans_post.push(x / y);
}
}
}
return ans_post.top();
}
#endif
int main()
{
std::ios::sync_with_stdio(false);
int N;
string p[30];
string expression;
cin >> N >> expression;
for (int i = 0; i < N; i++)
{
cin >> p[i];
}
for (int i = 0; i < (int)expression.size(); i++)
{
if (expression[i] == ',')
{
expression[i] = '*';
}
}
for (int i = 0; i <(int) expression.size() - 1; i++)
{
if (expression[i] == ')' && expression[i + 1] == '(')
{
expression.insert(i + 1, "+");
int counter = 0;
for (int j = i - 1; j >= 0; j--)
{
if (expression[j] == '(' && counter == 0)
{
expression.insert(j, "(");
break;
}
else if (expression[j] == ')')
{
counter--;
}
else if (expression[j] == '(')
{
counter++;
}
}
counter = 0;
for (int j = i + 4; j <(int) expression.size(); j++)
{
if (expression[j] == ')' && counter == 0)
{
expression.insert(j + 1, ")");
break;
}
else if (expression[j] == '(')
{
counter--;
}
else if (expression[j] == ')')
{
counter++;
}
}
}
}
for (int i = 0; i < (int)expression.size(); i++)
{
if ('A' <= expression[i] && expression[i] <= 'Z')
{
int pos = expression[i] - 'A';
expression.erase(i, 1);
expression.insert(i, p[pos]);
}
}
Calculator c;
c.trans_to_postfix_expression_to_s(expression);
cout << setprecision(4) << std::fixed << c.calculate_from_postfix_expression() << endl;
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。