2295 A DP Problem

問題概要

+,-,変数xのみで両辺が構成される一次方程式が与えられる。
この方程式の解が、一意に定まるならその値を切り捨てたものを、
そうでないならIMPOSSIBLE（不能）またはIDENTITY（不定）を出力せよ。

式の長さは260以下で、出現する数字は1000を超えない。

解法

構文解析する。括弧がないので楽だが、はまりやすいポイントが多い。

• マイナスの数を切り捨てる場合、-3.1は-4にする
• xは1*xに等しい

など。

ソースコード

int n; char in[300];
pi eval(int s,int t){
	int i=t-1;
	for(;i>s;i--)if(in[i]=='+'||in[i]=='-')break;
	if(i<=s){
		if(in[s]=='x')return mp(1,0);
		int d=0;
		for(i=s;i<t&&isdigit(in[i]);i++)d*=10,d+=in[i]-'0';
		return i<t?mp(d,0):mp(0,d);
	}
	pi a=eval(s,i),b=eval(i+1,t);
	if(in[i]=='-')b.first*=-1,b.second*=-1;
	return mp(a.first+b.first,a.second+b.second);
}
int main(){
	scanf("%d",&n);
	rep(i,n){
		scanf("%s",in);
		int e=0; for(;in[e];e++)if(in[e]=='=')break;
		pi a=eval(0,e),b=eval(e+1,strlen(in));
		int p=a.first-b.first,q=-a.second+b.second;
		
		if(p==0)puts(q?"IMPOSSIBLE":"IDENTITY");
		else printf("%d\n",(int)floor(q*1.0/p));
	}
	return 0;
}