tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

AOJ 1314 Matrix Calculator

WFも近いし最近あんまり構文解析やってないから今日は構文解析
問題文のBNFに解法が書いてある系問題。実数倍の存在を忘れないように。
あと手元だとスタックサイズ調整してやらないとsegmentation faultしました。


pairを使わないことが短い実装をするのに良いらしい…?

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;
struct mat{
	int v[110][110];
	int R;
	int C;
	mat(){
		R=C=0;
		for(int i=0;i<110;i++)
			for(int j=0;j<110;j++)
				v[i][j]=0;
	}
};
mat var[26];
int mod=32768;
char str[128];
int debug=0;
pair<mat,int> expr(int a);
pair<mat,int> term(int a);
pair<mat,int> fact(int a);
pair<mat,int> prim(int a);
pair<mat,int> matr(int a);
pair<mat,int> row(int a);
pair<mat,int> expr(int a){
	if(debug)printf("DEBUG EXPR IN %d\n",a);fflush(stdout);
	pair<mat,int> ret=term(a);
	while(str[ret.second+1]=='+'||str[ret.second+1]=='-'){
		pair<mat,int> tmp=term(ret.second+2);
		if(str[ret.second+1]=='+'){
			for(int i=0;i<ret.first.R;i++){
				for(int j=0;j<ret.first.C;j++)
					ret.first.v[i][j]=(ret.first.v[i][j]+tmp.first.v[i][j])%mod;
			}
		}else{
			for(int i=0;i<ret.first.R;i++){
				for(int j=0;j<ret.first.C;j++)
					ret.first.v[i][j]=(ret.first.v[i][j]-tmp.first.v[i][j]+mod)%mod;
			}
		}
		ret.second=tmp.second;
	}
	if(debug)printf("DEBUG EXPR OUT %d\n",ret.second);fflush(stdout);
	return ret;
}
pair<mat,int> term(int a){
	if(debug)printf("DEBUG TERM IN %d\n",a);fflush(stdout);
	pair<mat,int> ret=fact(a);
	while(str[ret.second+1]=='*'){
		pair<mat,int> tmp=fact(ret.second+2);
		if((tmp.first.R==1&&tmp.first.C==1)||(ret.first.R==1&&ret.first.C==1)){
			if(tmp.first.R*tmp.first.C==1){
				for(int i=0;i<ret.first.R;i++)	
					for(int j=0;j<ret.first.C;j++)
						ret.first.v[i][j]=(ret.first.v[i][j]*tmp.first.v[0][0])%mod;
			}else{
				int k=ret.first.v[0][0];
				for(int i=0;i<tmp.first.R;i++)
					for(int j=0;j<tmp.first.C;j++)
						ret.first.v[i][j]=(tmp.first.v[i][j]*k)%mod;
				ret.first.R=tmp.first.R;
				ret.first.C=tmp.first.C;
			}
			ret.second=tmp.second;
		}else{
			mat ans;
			ans.R=ret.first.R;
			ans.C=tmp.first.C;
			for(int i=0;i<ans.R;i++){
				for(int j=0;j<ans.C;j++){
					for(int k=0;k<ret.first.C;k++){
						ans.v[i][j]=(ans.v[i][j]+ret.first.v[i][k]*tmp.first.v[k][j]%mod)%mod;
					}
				}
			}
			ret.first=ans;
			ret.second=tmp.second;
		}
	}
	if(debug)printf("DEBUG TERM OUT %d\n",ret.second);fflush(stdout);
	return ret;
}
pair<mat,int> fact(int a){
	if(debug)printf("DEBUG FACT IN %d\n",a);fflush(stdout);
	if(str[a]=='-'){
		pair<mat,int> ret=fact(a+1);
		for(int i=0;i<ret.first.R;i++)
			for(int j=0;j<ret.first.C;j++)
				ret.first.v[i][j]=mod-ret.first.v[i][j];
		return ret;
	}else{
		return prim(a);
	}
}
pair<mat,int> prim(int a){
	if(debug)printf("DEBUG PRIM IN %d\n",a);fflush(stdout);
	pair<mat,int> ret;
	if(str[a]>='0'&&str[a]<='9'){
		int at=a;
		int num=0;
		while(str[at]>='0'&&str[at]<='9'){
			num*=10;
			num+=str[at]-'0';
			num%=mod;
			at++;
		}
		mat ans;
		ans.R=ans.C=1;
		ans.v[0][0]=num;
		ret.first=ans;
		ret.second=at-1;
	}else if(str[a]>='A'&&str[a]<='Z'){
		ret=make_pair(var[str[a]-'A'],a);
		ret.second=a;
	}else if(str[a]=='('){
		ret=expr(a+1);
		ret.second++;
	}else{
		ret=matr(a+1);
		ret.second++;
	}
	while(str[ret.second+1]=='('||str[ret.second+1]=='\''){
		if(str[ret.second+1]=='('){
			pair<mat,int> tmp1=expr(ret.second+2);
			pair<mat,int> tmp2=expr(tmp1.second+2);
			mat tmp;
			tmp.R=tmp1.first.C;
			tmp.C=tmp2.first.C;
			for(int i=0;i<tmp.R;i++){
				for(int j=0;j<tmp.C;j++){
				tmp.v[i][j]=ret.first.v[tmp1.first.v[0][i]-1][tmp2.first.v[0][j]-1];
				}
			}
			ret.first=tmp;
			ret.second=tmp2.second+1;
		}else{
			mat tmp;
			tmp.R=ret.first.C;
			tmp.C=ret.first.R;
			for(int i=0;i<tmp.R;i++)
				for(int j=0;j<tmp.C;j++)
					tmp.v[i][j]=ret.first.v[j][i];
			ret.first=tmp;
			ret.second++;
		}
	}
	if(debug)printf("DEBUG PRIM OUT %d\n",ret.second);fflush(stdout);
	return ret;
}
pair<mat,int> matr(int a){
	pair<mat,int> ret=row(a);
	while(str[ret.second+1]==';'){
		pair<mat,int> tmp=row(ret.second+2);
		for(int i=0;i<tmp.first.R;i++){
			for(int j=0;j<tmp.first.C;j++){
				ret.first.v[ret.first.R+i][j]=tmp.first.v[i][j];
			}
		}
		ret.first.R+=tmp.first.R;
		ret.second=tmp.second;
	}
	return ret;
}
pair<mat,int> row(int a){
	pair<mat,int> ret=expr(a);
	while(str[ret.second+1]==' '){
		pair<mat,int> tmp=expr(ret.second+2);
		for(int i=0;i<tmp.first.R;i++){
			for(int j=0;j<tmp.first.C;j++){
				ret.first.v[i][ret.first.C+j]=tmp.first.v[i][j];
			}
		}
		ret.first.C+=tmp.first.C;
		ret.second=tmp.second;
	}
	return ret;
}
int main(){
	int n;
	while(scanf("%d",&n),n){
		for(int i=0;i<26;i++)var[i]=mat();
		gets(str);
		while(n--){
			gets(str);
			int to=str[0]-'A';
			pair<mat,int> ret=expr(2);
			var[to]=ret.first;
			for(int i=0;i<var[to].R;i++){
				for(int j=0;j<var[to].C;j++){
					if(j)printf(" ");
					printf("%d",var[to].v[i][j]);
				}
				printf("\n");
			}
		}
		printf("-----\n");
	}
}