POJ-2106: Boolean Expressions

keyword

構文解析　C++

問題概要

論理式を構文解析した結果を出力する問題。

解法

やるだけ。BNFは、
expr := term ( '|' term )^*
term := fact ( '&' fact )^*
fact := 'V' | 'F' | '(' expr ')' | '!' fact

#include <cstdio>
using namespace std;

char buf[1009];
char input[1009];
int p;

bool expr();
bool term();
bool fact();

bool expr(){
	bool ret = term();
	while(input[p] == '|'){
		p++;
		ret |= term();
	}
	return ret;
}

bool term(){
	bool ret = fact();
	while(input[p] == '&'){
		p++;
		ret &= fact();
	}
	return ret;
}

bool fact(){
	if(input[p] == '('){
		p++;
		bool ret = expr();
		p++;
		return ret;
	}
	else if(input[p] == 'V'){
		p++;
		return true;
	}
	else if(input[p] == 'F'){
		p++;
		return false;
	}
	else if(input[p] == '!'){
		p++;
		return !fact();
	}
}

bool solve(){
	p = 0;
	for(int i=0; buf[i]; i++){
		if(buf[i]!=' ') input[p++] = buf[i];
	}
	input[p] = '\0';
	p = 0;
	return expr();
}

int main(){
	int cnt = 1;
	while(gets(buf)){
		printf("Expression %d: %c\n", cnt++, solve()?'V':'F');
	}
	return 0;
}