tozangezan's diary

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

AOJ1155,0264

ICPCとかいうものがあるので、構文解析を練習することにしました。

1155
構文解析とは何か、ということを知りました。

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
char str[100];
int v[3];
int eq(int a,int b);
int ter(int a,int b){
    if(str[a]=='(')return eq(a+1,b-1);
    if(str[a]=='-')return 2-ter(a+1,b);
    if(str[a]>'A')return v[str[a]-'P'];
    return str[a]-'0';
}
int fac(int a,int b){
    int now=0;
    int ret=2;
    int las=a;
    for(int i=a;i<b;i++){
        if(str[i]=='(')now++;
        if(str[i]==')')now--;
        if(now==0&&str[i]=='*'){
            ret=min(ret,ter(las,i));
            las=i+1;
        }
    }
    return min(ret,ter(las,b));
}
int eq(int a,int b){
    int now=0;
    int ret=0;
    int las=a;
    for(int i=a;i<b;i++){
        if(str[i]=='(')now++;
        if(str[i]==')')now--;
        if(now==0&&str[i]=='+'){
            ret=max(ret,fac(las,i));
            las=i+1;
        }
    }
    return max(ret,fac(las,b));
}
int main(){
    while(1){
        scanf("%s",str);
        if(str[0]=='.')return 0;
        int n=strlen(str);
        int ret=0;
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                for(int k=0;k<3;k++){
                    v[0]=i;
                    v[1]=j;
                    v[2]=k;
                    ret+=eq(0,n)/2;
                }
        printf("%d\n",ret);
    }
}

0264
BNFを変な風に再帰する、ということを学びました。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char str[131072];
char S[131072];
int inv[46000];
bool ok;
int p;
pair<int,int> eq(int a);
pair<int,int>ter(int a){
	if(S[a]=='('){
		pair<int,int> t=eq(a+1);
		t.second++;
	//	printf("t%d %d %d\n",a,t.first,t.second);
		return t;
	}else{
		int at=a;
		int now=0;
		while('0'<=S[at]&&S[at]<='9'){
			now=(now*10+S[at]-'0')%p;
			at++;
		}
	//	printf("t%d %d %d\n",a,now,at-1);
		return make_pair(now,at-1);
	}
}
pair<int,int>fac(int a){
	pair<int,int> t=ter(a);
	int ret=t.first;
	while(S[t.second+1]=='*'||S[t.second+1]=='/'){
		if(S[t.second+1]=='*'){
			t=ter(t.second+2);
			ret=ret*t.first%p;
		}else{
			t=ter(t.second+2);
			ret=ret*inv[t.first]%p;
			if(t.first==0)ok=false;
		}
	//	t.second++;
	}
//	printf("f%d %d %d\n",a,ret,t.second);
	return make_pair(ret,t.second);
}
pair<int,int> eq(int a){
	pair<int,int> t=fac(a);
	int ret=t.first;
	while(S[t.second+1]=='+'||S[t.second+1]=='-'){
		if(S[t.second+1]=='+'){
			t=fac(t.second+2);
			ret=(t.first+ret)%p;
		}else{
			t=fac(t.second+2);
			ret=(p+ret-t.first)%p;
		}
	//	t.second++;
	}
//	printf("e%d %d %d\n",a,ret,t.second);
	return make_pair(ret,t.second);
}
int main(){
	while(1){
		gets(str);
		if(str[0]=='0')return 0;
		ok=true;
		p=0;
		int at=0;
		while('0'<=str[at]&&str[at]<='9'){
			p*=10;
			p+=str[at++]-'0';
		}
		inv[1]=1;
		for(int i=2;i<p;i++)inv[i]=p-p/i*inv[p%i]%p;
		at++;
		int v=0;
		for(int i=at;str[i];i++){
			if(str[i]!=' ')S[v++]=str[i];
		}
		S[v]=0;
		int res=eq(0).first;
		if(!ok)printf("NG\n");
		else printf("%s = %d (mod %d)\n",S,res,p);
		//printf("%s\n%s\n",str,S);
	}
}