2017 计蒜之道 初赛 第二场第B题(简单)题解

2017 计蒜之道 初赛 第二场第B题(简单)题解

时间&空间

1000ms

262144K

题目描述

今年,百度的科学计算器进行了重大更新,可以计算更为复杂的表达式了。

定义表达式中存在加减运算、括号、函数调用、强制类型转换这几种运算。其中数值的类型有整型与浮点型两种。并且,

  • 整型与整型加减运算的结果为整型;
  • 整型与浮点型加减运算结果为浮点型;
  • 浮点型与浮点型加减运算结果为浮点型。

强制类型转换符 包括int(x)与float(x),其中float(x)运算符可以将数值x的类型强制转为浮点型,int(x)运算符可以将数值x的类型强制转为整型。对于浮点型转整型,采用截尾法,例如:int(1.6)=1,int(-1.6)=-1等等。

例如,

  • int(10.9999)=10;
  • float(10)=10.000000;
  • int(10.9999)+float(1)=11.000000;
  • int(1.0)+(100-40)=61。

除此以外,还可以定义一系列函数,形如:

  • fun(x,y)=x+y+fun2(y)
  • fun2(x)=fun3()+int(x)
  • fun3()=61

函数的变量名和函数名均由一个或多个大小写字母以及数字组成,并且由大小写字母开头。保证:变量名与函数名不为int或float;同一函数的不同参数的参数名互不相同;函数名互不相同。函数参数不超过两个,函数之间可能存在相互调用关系,相互调用传参时,各个参数保证均为单一变量(既不是表达式也不是数字常量)。例如f1(x,y)=f2(y,x)+f3(x)+f4()是合法的,而f(x)=f2(x+x)+f3(61)是不合法的(因为函数相互调用时参数不为表达式或数字常量)。

对于给定表达式,百度的科学计算器需要算出该表达式的结果。

输入格式

第一行输入一个整数 n(0≤n≤1000),表示有 n 个函数。

接下来一共输入 n+1 行,对于前 n 行,每行一个字符串,分别代表 n 个函数,每个函数长度均不超过 50 个字符,字符串中只包含加号+、减号-、括号()、数字常量、强制类型转换以及函数调用。输入数据保证所有表达式合法,表达式中没有空格。

最后一行为一个表达式,表示需要求解的表达式,表达式长度不超过 1000,并且这一表达式中出现函数调用的次数不超过 3 次。

输入数据保证数字常量以及计算过程中数值绝对值均不超过 10^​12​​,对于浮点型数值常量,保证小数点后不超过 6 位。

输入数据保证求解表达式及函数表达式出现的数字常量均为非负数,但计算中间结果不一定非负。

对于简单版本:n=0,在满足题意前提下,求解表达式中不存在强制类型转换int()、float()及函数调用;

对于中等版本:n≤3,在满足题意前提下,函数之间不存在相互调用的情况。函数的参数数量均为 111;

对于困难版本:满足上述题意中的条件,没有额外的限制。

输出格式

输出为一行,即表达式结果,对于浮点型结果,保留到小数点后 666 位。对于表达式无法求解的情况(例如循环调用),给出No Answer。

样例输入1

0
5.0-(4-5.1)

样例输出1

6.100000

样例输入2

3
func1(x)=x+1
func2(y)=y+1
func3(z)=z+int(1.9)
func1(1)+func2(1)+func3(1)

样例输出2

6

样例输入3

2
Haha(x)=Haha1(x)
Haha1(a)=Haha(a)
Haha(61)

样例输出3

No Answer

AC代码

#include <iostream>
#include <stack>
#include <sstream>
#include <map>
#include <cstdio>
#include <string>
#include <queue>

using namespace std;

stack<char> op;
stack<string> postexp;
stack<string> postexp1;
stack<double> postexpnum;
map<char,int> lpri;
map<char,int> rpri;

int flag=0;
int main()
{
    lpri['=']=0;
    lpri['(']=1;
    lpri['+']=3;
    lpri['-']=3;
    lpri['*']=5;
    lpri['/']=5;
    lpri[')']=6;

    rpri['=']=0;
    rpri['(']=6;
    rpri['+']=2;
    rpri['-']=2;
    rpri['*']=4;
    rpri['/']=4;
    rpri[')']=1;
    int N;
    cin>>N;
//    while(N--)
    {
        string str;
        cin>>str;
        str=str+'=';
        for(unsigned int i=0;i<str.size();i++)
            if(str[i]=='.')
        {
            flag=1;
            break;
        }
        op.push('=');
        string tmpnum;
        // cout<<str<<endl;
        for(unsigned int i=0;i<str.length();i++)
        {
            if(rpri.count(str[i]))
            {
                if(tmpnum.length()!=0)
                {
                    postexp.push(tmpnum);
                    tmpnum.clear();
                }

                if(rpri[str[i]]>lpri[op.top()])
                    op.push(str[i]);
                else
                {
                    if(str[i]==')')
                    {
                        while(op.top()!='(')
                        {
                            string str1;
                            str1+=op.top();
                            op.pop();
                            postexp.push(str1);
                        }
                        op.pop();
                    }
                    else
                    {
                        while(lpri[op.top()]>rpri[str[i]])
                    {
                            string str1;
                            str1+=op.top();
                            op.pop();
                            postexp.push(str1);
                        }
                        op.push(str[i]);
                    }
                }
            }
            else
            {
                tmpnum+=str[i];
            }
        }
        while(!postexp.empty())
        {
            postexp1.push(postexp.top());
            postexp.pop();
        }
        while(!postexp1.empty())
        {
            double num;
            stringstream ss;
            if(postexp1.top()=="+")
            {
                num=postexpnum.top();
                postexpnum.pop();
                num+=postexpnum.top();
                postexpnum.pop();
                postexpnum.push(num);

            }
            else if(postexp1.top()=="-")
            {
                num=postexpnum.top();
                postexpnum.pop();
                num=postexpnum.top()-num;
                postexpnum.pop();
                postexpnum.push(num);

            }
            else if(postexp1.top()=="*")
            {
                num=postexpnum.top();
                postexpnum.pop();
                num*=postexpnum.top();
                postexpnum.pop();
                postexpnum.push(num);

            }
            else if(postexp1.top()=="/")
            {
                num=postexpnum.top();
                postexpnum.pop();
                if(num==0)
                {
                    cout<<"No Answer"<<endl;
                    return 0;
                }

                num=postexpnum.top()/num;
                postexpnum.pop();
                postexpnum.push(num);
            }
            else
            {
                ss<<postexp1.top();
                ss>>num;
                postexpnum.push(num);
            }

            postexp1.pop();
        }
        //cout<<postexpnum.top();
        if(flag==0)
            cout<<(long long int)(postexpnum.top())<<endl;
        else
            printf("%.6lf\n",postexpnum.top());
        postexpnum.pop();
    }
    return 0;
}

总结

a题没有看懂是什么意思, b题可以说特别简单但是我在比赛的时候还是没有写出来.
模板修改一下就可以了.

发表评论