题解：P1812 区间运算

update:2025.3.8

本题解进行了修改，对于 $-0.000$ 的情况进行了修改。同时感谢KobeBeanBryantCox的提醒。

题目大意

给定一个区间运算的表达式，让你按照规则进行运算得出结果。如果有一个区间运算形如：

\frac {[a,b]}{[c,d]}

并且

[c.d]

里面包含

0

，就输出 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]=[-b,-a]$ （这里的取反使用 ! 进行标记）
对于区间 $[a,b]$ ，如果作为除数是包含 $0$ ，那么 $a \times b \le 0$ 。

综上，写出结构体储存与运算模块：

CPP

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$ 这个情况。
小小的警告：有一个点给出的区间不保证左边界小于右边界。

其余就按照中缀转后缀模拟即可。

CPP

#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 一起用，不然会寄。

题解：P1812 区间运算

文章操作

题目大意

总体思路

警钟撅烂

相关推荐

评论

题解：P1812 区间运算