题解：P1812 区间运算
xiaozhao_
·
·
题解
诚挚感谢 @KobeBeanBryantCox 的指出问题和$hack$数据
## 题目大意：
给定多个以中缀表达式表达的区间运算，求出其最终答案。
## 思路：
很明显，只在中缀表达式的基础上加入区间运算便可 AC 本题。
**1.中缀表达式：**
对中缀表达式比较陌生的洛友可以先做一本通上的[这道题](http://ybt.ssoier.cn:8088/problem_show.php?pid=1358) ~~（洛谷上没有中缀表达式模板题(lllQωQ)）~~。
- 对于一个没有区间运算的中缀表达式 $s$，我们首先需要知道运算优先级。读题可以很容易得出，运算优先级为 $\text{小括号} > \text{取相反数} > \text{乘除} > \text{加减}$。
- 其次，我们需要将中缀转后缀方便计算（我选择边转边算，这样方便处理）。先建立两个栈，分别是数字栈 $sp$ 和符号栈 $sc$。然后将读入到的数字和运算符分别依次存入 $sp$ 和 $sc$。当遇到 $sc_{top}$ 的优先级**大于等于** $s_i$ 的优先级时，我们需要不停得计算**直到 $sc_{top}$ 的优先级小于 $s_i$ 的优先级**，以保证高优先级的先运算。为什么是大于等于？好问题，比如说当该中缀表达式为 $8\times6\div4\times2$ 时，如果只是将运算优先级大于自己的先运算，那么最后计算的顺序就变成了先算 $4\times2$，很快就可以这**不符合**同级运算按从左到右的顺序的的规则。
- 小括号比较特殊，如果按按上面的方法遇到小括号时前面所有都会进行计算，这很明显是不对的，所以要特判。并且，对于**每一个**右括号，我们要**一直计算**到找到与它**对应的左括号**为止。
- 最后，我们只需计算转换后的后缀表达式即可得出最终答案。
**2.区间运算：**
不会区间运算的洛友走这边(☞ﾟヮﾟ)☞[区间运算详解](https://blog.csdn.net/m0_72410588/article/details/130811472)。
看完上面的链接就应该算是区间运算入门了，以下是我们需要的内容：
对于两个区间 $[a,b]$ 和 $[c,d]$，它们的加减乘除运算结果分别为：
- 加法：$[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)]$；
- 除法：$[a, b]\div[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})]$ (其中 $c$ 和 $d$ 不能包含 $0$)。
3.**注意**：
（1）一个包含 $0$ 的区间作为除数：
- 小学三年级的数学老师曾经告诉我们：“**除数不能为 $0$！**”区间运算也是如此。如何判断区间 $[a,b]$ 是否包含 $0$ 呢？已知 $0$ 是正数和负数的分界，那么包含 $0$ 的区间 $[a,b]$ 中要么 $a$ 与 $b$ 异号，要么 $a$ 或 $b$ 有一个数为 $0$。因此，**判断 $ab\le0$ 便可知道区间 $[a,b]$ 是否包含 $0$。**
（2）区分取相反数符号和减号：
- 如何区分减号和取反数符号？我认为，**一个意义为取相反数的减号只会出现在运算符后。**
- 为了方便后面的计算，我们遇到一个意义为取相反数的减号时将它的值定为 $1$。
## AC 代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=92;
map<char,int> p{{'+',0},{'-',0},{'*',1},{'/',1},{1,2},{'(',9}}; //存储运算优先级。
struct pdd{double l,r;}sp[N]; //手写栈 si 存储区间 [l,r]。
bool z; //特判除数为 0 的情况。
char s[N],sc[N];
int n,t1,t2; //t1 为栈 si 的栈顶位置，t2 为 sc 的栈顶位置。
inline bool isnum(char c){return c>=48&&c<=57;} //判断是否为数字。
inline void readn(int &i,double &x){
x=0;
int z=0,t=0,cnt=0; //z 存储整数部分，t 存储小数部分，cnt 存储小数位数。
bool f=0;
if(s[i]=='-') f=1;
else z=s[i]^48;
while(isnum(s[++i])) z=(z<<3)+(z<<1)+(s[i]^48);
if(s[i]=='.') //注意，有小数点才会有小数部分。
while(isnum(s[++i])) t=(t<<3)+(t<<1)+(s[i]^48),cnt++;
x=z+1.0*t/pow(10,cnt);
if(f) x=-x;
} //读入浮点数。
inline void calc(){
char op=sc[t2--];
pdd t=sp[t1--];
if(op==1){
sp[++t1]={-t.r,-t.l};
return;
} //取相反数。
double a=sp[t1].l,b=sp[t1].r,c=t.l,d=t.r;
if(op=='+') sp[t1]={a+c,b+d};
else if(op=='-') sp[t1]={a-d,b-c};
else if(op=='*')
sp[t1]={min(a*c,min(a*d,min(b*c,b*d))),max(a*c,max(a*d,max(b*c,b*d)))};
else{
if(c*d<=0){ //[c,d] 这个是个包含 0 的区间。
z=1;
return;
}
sp[t1]={min(a/c,min(a/d,min(b/c,b/d))),max(a/c,max(a/d,max(b/c,b/d)))};
}
} //计算。
int main(){
while(~scanf("%s",s)){
z=t1=t2=0; //初始化。
n=strlen(s);
int num=0;
for(int i=0;i<n;i++){
if(s[i]=='['){ //读入区间。
readn(++i,sp[++t1].l);
readn(++i,sp[t1].r);
if(sp[t1].l>sp[t1].r) swap(sp[t1].l,sp[t1].r); //保证 l<r。
}else{
if(s[i]==')'){ //遇到右括号时需要将整个括号内全部计算。
while(!z&&sc[t2]!='(') calc();
t2--;
}else{ //剩下的只能是运算符。
if(s[i]=='-'&&s[i-1]!=']'&&s[i-1]!=')')
s[i]=1; //把取相反数的看作一个自定义的符号方便区分。
while(!z&&t2&&sc[t2]!='('&&p[sc[t2]]>=p[s[i]])
calc(); //将优先级比自己高或等于自己的运算全部算了。
sc[++t2]=s[i];
}
}
if(z) break; //有除数包含零直接跳出循环。
}
while(!z&&t2) calc(); //把剩下的全部算完。
if(z) printf("Division by zero");
else printf("[%.3lf,%.3lf]",sp[1].l==0?0:sp[1].l,sp[1].r==0?0:sp[1].r);
putchar(10);
}
return 0;
}
```
后序：题解有界，帮助无限，希望这篇题解可以帮助屏幕前的你ヾ(≧▽≦*)o。