読者です 読者をやめる 読者になる 読者になる

kengo92iの日記

プログラミングとかやったことの記録を書いていきます。

AOJ-1155 : 如何に汝を満足せしめむ? いざ数え上げむ…

How can I satisfy thee? Let me count the ways... | Aizu Online Judge

三値論理という、真, 偽, 未知 (0,1,2) がある論理式が与えられる。変数(P,Q,R)の値を変化させて(P,Q,R) の三つ組が何通りあるかを答える問題。演算子'-', '*', '+' (NOT,AND,OR)の3つが存在している。


与えられる式は中置記法で書かれているので、処理し易いように逆ポーランド記法に変換します。逆ポーランド記法に変換するのには「操車場アルゴリズム」というのがあります。

逆ポーランド記法に変換すればスタックを使って計算するだけで答えが求められます。P,Q,Rの3つの値の組み合わせは「3*3*3=27通り」なので全探索して問題ないです。答えが「2」になった回数を求めて出力します。

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1155&lang=jp

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>
#include<stack>
#include<queue>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

int NOT(int x){ return 2-x; }
int AND(int x, int y){ return min(x,y); }
int OR(int x, int y){ return max(x,y); }
bool is_operator(char op){
	return (op == '-' || op == '*' || op == '+');
}

string postfix(string fml)
{
	string res="";
	stack<char> st;
	queue<char> que;
	rep(i, fml.size())
	{
		if(is_operator(fml[i])){
			while(!st.empty()){
				if(!is_operator(st.top())) break;
				if(fml[i] == '-') break;
				que.push(st.top());
				st.pop();
			}
			st.push(fml[i]);
		}
		else if(fml[i] == '('){
			st.push(fml[i]);
		}
		else if(fml[i] == ')'){
			while(!(st.top() == '(')){
				que.push(st.top());
				st.pop();
			}
			st.pop();
		}
		else{
			que.push(fml[i]);
		}
	}

	while(!st.empty()){
		que.push(st.top());
		st.pop();
	}

	while(!que.empty()){
		res += que.front();
		que.pop();
	}
	return res;
}

int solve(int p, int q, int r, string fml)
{
	int res=0;
	stack<int> st;
	rep(i,fml.size())
	{
		if(fml[i] == 'P'){
			st.push(p);
		}
		else if(fml[i] == 'Q'){
			st.push(q);
		}
		else if(fml[i] == 'R'){
			st.push(r);
		}
		else if(isdigit(fml[i])){
			st.push(fml[i]-'0');
		}
		else if(fml[i] == '-'){
			int x = st.top();
			st.pop();
			st.push(NOT(x));
		}
		else if(fml[i] == '*'){
			int x = st.top(); st.pop();
			int y = st.top(); st.pop();
			st.push(AND(x,y));
		}
		else if(fml[i] == '+'){
			int x = st.top(); st.pop();
			int y = st.top(); st.pop();
			st.push(OR(x,y));
		}
	}

	return (st.top() == 2) ? 1 : 0;
}

int main()
{
	string formula;
	while(cin >> formula)
	{
		if(formula == ".") break;

		formula = postfix(formula);

		int ans=0;
		rep(p,3){
			rep(q,3){
				rep(r,3){
					ans += solve(p,q,r,formula);
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}