POJ 2106：Boolean Expressions 计算布尔表达式 - 堆栈

题意：bool表达式求值，V：true；F：false

题解：堆栈+优先级判定

给的输出样例比答案少一行==

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 110;
int val[N], vtop, op[N], otop;//数值栈；运算符栈；栈顶指针
void ins(int b){
	while(otop && op[otop - 1] == 3){
		b = !b;
		--otop;
	}
	val[vtop++] = b;
}
void calc(){//双目运算
	int b = val[--vtop];
	int a = val[--vtop];
	int opr = op[--otop];
	int c = (a & b);
	if(opr == 1)
		c = (a | b);
	ins(c);
}

int main(){
	int loop = 0;
	char c;
	while((c = getchar()) != EOF){
		vtop = otop = 0;
		do{
			if(c == '(')
				op[otop++] = 0;
			else if(c == ')'){
				while(otop && op[otop - 1] != 0)
					calc();
				--otop;
				ins(val[--vtop]);
			}
			else if(c == '!')
				op[otop++] = 3;
			else if(c == '&'){
				while(otop && op[otop - 1] >= 2)
					calc();
				op[otop++] = 2;
			}
			else if(c == '|'){
				while(otop && op[otop - 1] >= 1)
					calc();
				op[otop++] = 1;
			}
			else if(c == 'V' || c == 'F'){
				ins(c == 'V' ? 1 : 0);
			}
		}while((c = getchar()) != '\n' && c != EOF);
		
		while(otop)
			calc();
		printf("Expression %d: %c\n", ++loop, (val[0] ? 'V' : 'F'));
	}
	return 0;
}