电路稳定性

电路稳定性

时间: 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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注