2348-Testing Circuits

問題概要

論理式が与えられる．この式を満たすような変数の値の組み合わせの数を求めよ．ただし，同じ変数は一度しか表われない．

解法

構文解析する．スタックオーバーフローに注意する．

実装(C++)

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>
using namespace std;
typedef unsigned char uchar;
typedef unsigned long long ull;
#define REP(i,x) for(long long i=0;i<(long long)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(long long i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)

template<typename T>
ostream &operator<<(ostream &os,vector<T> &a){
	copy(a.begin(),a.end(),ostream_iterator<T>(os," "));
	os<<endl;
	return os;
}
char *s;
typedef pair<long long,long long> P;
P expression();
P term();
P factor();
long long moduler(long long k){
	return k%1000000007;
	       //1000000007.
}
P ord(P a,P b){
	return P(moduler((long long)b.first*a.second+(long long)a.first*b.second+(long long)a.first*b.first),moduler((long long)a.second*b.second));
}
P notd(P a){
	return P(moduler(a.second),moduler(a.first));
}
struct S{
	P now;
	long long back;
};
stack<S>sta;
void solve(){
	P result;
	P now;
	S tmp;
	long long t;
	expr:
	tmp.now=now;
	tmp.back=0;
	sta.push(tmp);
	goto term;
	back_0:
	now=result;
	while((*s)=='|'){
		s++;
		tmp.now=now;
		tmp.back=1;
		sta.push(tmp);
		goto term;
		back_1:
		now=ord(now,result);
	}
	if(sta.empty()){
		cout<<now.first<<endl;
		return;
	}else{
		result=now;
		goto __back;
	}
	term:

	tmp.now=now;
	tmp.back=2;
	sta.push(tmp);
	goto factor;
	back_2:
	now=result;
	loop2:
	if(*s!='&')goto exit_loop2;

	s++;
	tmp.now=now;
	tmp.back=3;
	sta.push(tmp);
	goto factor;
	back_3:
	now=notd(ord(notd(now),notd(result)));
	goto loop2;
	exit_loop2:
	result=now;
	goto __back;
	factor:
	now=P(0,0);
	while(*s=='~'){
		now.first=!now.first;
		s++;
	}
	if(*s=='('){
		s++;
		tmp.now=now;
		tmp.back=4;
		sta.push(tmp);
		goto expr;
		back_4:
		s++;
		result=now.first?notd(result):(result);
		goto __back;
	}
	s++;
	result=P(1,1);
	goto __back;
	__back:
	t=sta.top().back;
	now=sta.top().now;
	sta.pop();
	if(t==0){
		goto back_0;
	}else if(t==1){
		goto back_1;
	}else if(t==2){
		goto back_2;
	}else if(t==3){
		goto back_3;
	}else if(t==4){
		goto back_4;
	}
}

char tmp[1111111];
char is[1111111];
int main(){
	cin >> is;
	long long now=0;
	for(long long i=0;is[i];i++){
		if(isdigit(is[i]))continue;
		tmp[now++]=is[i];
	}
	now=0;
	memset(is,0,sizeof(is));
	for(long long i=0;tmp[i];i++){
		is[i]=tmp[i];
	}
	s=is;

	solve();
}