题解：P1812 区间运算
本题解进行了修改，对于
-0.000 的情况进行了修改。同时感谢KobeBeanBryantCox的提醒。
题目大意
给定一个区间运算的表达式，让你按照规则进行运算得出结果。如果有一个区间运算形如：Division by zero。
总体思路
首先，我们分析一下运算的规则和求解方法：
-
[a,b]+[c,d]=[a+c,b+d] -
[a,b]-[c,d]=[a-d,b-c] -
[a,b] \times [c,d]=[\min(ac,ad,bc,bd),\max(ac,ad,bc,bd)) -
\frac{[a,b]}{[c,d]}=[\min(\frac{a}{c},\frac{a}{d},\frac{b}{c},\frac{b}{d}),\max(\frac{a}{c},\frac{a}{d},\frac{b}{c},\frac{b}{d})] -
- 对于区间
[a,b] ，如果作为除数是包含0 ，那么a \times b \le 0 。
综上，写出结构体储存与运算模块：
struct Node{
double l,r;
bool check(){return (l*r<=0);}
Node operator + (Node a){return {l+a.l,r+a.r};}
Node operator - (Node a){return {l-a.r,r-a.l};}
Node operator * (Node a){return {min({l*a.l,l*a.r,r*a.l,r*a.r}),max({l*a.l,l*a.r,r*a.l,r*a.r})};}
Node operator / (Node a){return {min({l/a.l,l/a.r,r/a.l,r/a.r}),max({l/a.l,l/a.r,r/a.l,r/a.r})};}
Node operator ! (){return {-r,-l};}
};其次，将中缀表达式转后缀表达式，没学过的可以参见这里（反正我觉得讲的挺好的）。具体过程就不详细说明，主要有以下几点：
- 如果栈顶的字符优先级高于或等于现在进入栈的符号的优先级，就一直计算直到不满足不满足上文条件为止。
- 读入右括号之后，一直计算到左括号出现，然后停止计算。
- 中间一定要记得判断除法区间包含
0 这个情况。 - 小小的警告：有一个点给出的区间不保证左边界小于右边界。
其余就按照中缀转后缀模拟即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Node{
double l,r;
bool check(){return (l*r<=0);}
Node operator + (Node a){return {l+a.l,r+a.r};}
Node operator - (Node a){return {l-a.r,r-a.l};}
Node operator * (Node a){return {min({l*a.l,l*a.r,r*a.l,r*a.r}),max({l*a.l,l*a.r,r*a.l,r*a.r})};}
Node operator / (Node a){return {min({l/a.l,l/a.r,r/a.l,r/a.r}),max({l/a.l,l/a.r,r/a.l,r/a.r})};}
Node operator ! (){return {-r,-l};}
};
string s;
stack<char>fh;
stack<Node>data;
map<char,int>high;
bool division=false;
int read(int now)
{
bool point=false;
bool zf=false;
Node ret;
int a1,a2,cnt;
a1=0;
a2=0;
cnt=0;
int i;
for(i=now;i<s.length();i++)
{
if(s[i]=='-')zf=true;
if(s[i]>='0' && s[i]<='9')
{
if(point)a2=a2*10+(s[i]-'0'),cnt++;
else a1=a1*10+(s[i]-'0');
}
if(s[i]=='.')point=true;
if(s[i]==',')
{
point=false;
ret.l=a1+a2*1.0/pow((int)10,cnt);
if(zf)ret.l=-ret.l;
zf=false;
a1=0;
a2=0;
cnt=0;
}
if(s[i]==']')
{
ret.r=a1+a2*1.0/pow((int)10,cnt);
if(zf)ret.r=-ret.r;
break;
}
}
if(ret.l>ret.r)swap(ret.l,ret.r);
data.push(ret);
return i;
}
void cal()
{
char tp=fh.top();
fh.pop();
if(tp=='+')
{
Node a=data.top();
data.pop();
Node b=data.top();
data.pop();
data.push(b+a);
}
if(tp=='-')
{
Node a=data.top();
data.pop();
Node b=data.top();
data.pop();
data.push(b-a);
}
if(tp=='*')
{
Node a=data.top();
data.pop();
Node b=data.top();
data.pop();
data.push(b*a);
}
if(tp=='/')
{
Node a=data.top();
data.pop();
Node b=data.top();
data.pop();
if(a.check())
{
division=true;
return;
}
data.push(b/a);
}
if(tp=='!')
{
Node a=data.top();
data.pop();
data.push(!a);
}
}
void init()
{
high['+']=high['-']=1;
high['*']=high['/']=2;
high['!']=3;
high['(']=4;
}
void change()
{
string ret="";
for(int i=0;i<s.length();i++)
if(s[i]!=' ')
ret+=s[i];
s=ret;
}
signed main()
{
init();
while(getline(cin,s))
{
change();
division=false;
for(int i=0;i<s.length();i++)
{
if(s[i]=='[')
i=read(i);
if(s[i]==')')
{
if(fh.top()=='(')fh.pop();
else
{
while(!fh.empty() && fh.top()!='(' && high[fh.top()]>=high[s[i]])
{
cal();
if(division)
{
printf("Division by zero\n");
break;
}
}
fh.pop();
}
}
else if(s[i]!=']')
{
char ys=s[i];
if(ys=='-' && (i==0||s[i-1]!=']'&&s[i-1]!=')'))ys='!';
while(!fh.empty() && fh.top()!='('&&high[fh.top()]>=high[ys])
{
cal();
if(division)
{
printf("Division by zero\n");
break;
}
}
if(s[i]=='-' && (i==0||(s[i-1]!=']'&&s[i-1]!=')')))
{
fh.push('!');
}
else fh.push(s[i]);
}
if(division)
{
break;
}
}
if(division)
{
while(!fh.empty())fh.pop();
while(!data.empty())data.pop();
}
else
{
while(!fh.empty())
{
cal();
if(division)
{
printf("Division by zero\n");
break;
}
}
if(division)
{
while(!fh.empty())fh.pop();
while(!data.empty())data.pop();
}
if(division)continue;
if(abs(data.top().l)==0)data.top().l=0;
if(abs(data.top().r)==0)data.top().r=0;
printf("[%.3lf,%.3lf]\n",data.top().l,data.top().r);
data.pop();
}
}
return 0;
}警钟撅烂
千万不要开了 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);，然后又把 printf 和 cout 一起用，不然会寄。