自动搬运

查看原文

来自洛谷，原作者为

	xiaozhao_ I want to fry myself

搬运于2025-08-24 21:30:36，当前版本为作者最后更新于2024-07-26 10:57:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$2025.7.14$修：修复了输出$-0$出现的情况。

诚挚感谢 @KobeBeanBryantCox 的指出问题和$hack$数据

题目大意：

给定多个以中缀表达式表达的区间运算，求出其最终答案。

思路：

很明显，只在中缀表达式的基础上加入区间运算便可 AC 本题。

1.中缀表达式：

对中缀表达式比较陌生的洛友可以先做一本通上的这道题 （洛谷上没有中缀表达式模板题(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.区间运算：

不会区间运算的洛友走这边(☞ﾟヮﾟ)☞区间运算详解。

看完上面的链接就应该算是区间运算入门了，以下是我们需要的内容：

对于两个区间 $[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 代码：

#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。