[表达式]真假计算

题目描述

有一棵树，不一定是二叉树。
所有叶子节点都是 True 或者 False。
对于从上往下奇数层的非叶子节点是 and，偶数层非叶子节点为 or。
树上每个节点的值是所有孩子节点的值进行该节点的运算操作。
判断一棵树能否砍掉，最快的方法就是从叶子节点一路“与” 和 “或” 到根节点，得到整颗树的真假值后进行决断。

树以简单的括号序列给出：上图可以描述为 $((A(BC))(DE))$。

输入格式

数据包括若干组，每组数据包含一行一个字符串，输入 $()$ 表示结束。

输出格式

每组数据输出一行，包含：数据编号，点，空格，true 或 false。

样例

样例输入1：

((F(TF))(TF))
(TFT)
((TFT)T)
()

样例输出1

1. false
2. false
3. true

数据范围

对于 $10\%$ 的数据：每行只包含一对括号；
对于 $30\%$ 的数据：只有嵌套的括号，没有并列的括号；
对于 $100\%$ 的数据：测试数据少于 $1000$ 组，字符串长度小于 $32000$。

题解

直接进行递归，记录层数。

1. 如果当前字符为 (，说明要进入下一层，进行下一层递归。
2. 如果当前字符为 )，说明当前层结束，返回答案。
3. 如果当前字符为 T 或 F，计算答案。

判断结束判断字符串是不是 () 即可。

最后注意输入用 getchar，不要用 scanf。

int dfs(int y){
	char x = ' ';
	int sum = -1;//答案
	while(x != '\n'){
		x = getchar();
		if(x == '\n'){//下一行
			return sum;
		}
		if(x == '('){
			//递归
			int u = dfs(y + 1);
			//计算答案
			if(sum == -1){
				sum = u;
			}
			else if(y % 2 == 0){
				sum = sum & u;
			}
			else{
				sum = sum | u;
			} 
			continue;
		}
		if(x == ')'){//返回
			return sum;
		}
		//计算答案
		if(sum == -1){
			sum = (x == 'T');
		}
		else if(y % 2 == 0){
			sum = sum & (x == 'T');
		}
		else{
			sum = sum | (x == 'T');
		}
	}
	return sum;
}
int main(){
	int s = 0;//数据编号
	while(1){
		++ s;
		int u = dfs(-1);
		if(u == -1){
			return 0;
		} 
		printf("%d. ", s);
		if(u){
			printf("true\n");
		}
		else{
			printf("false\n");
		}
	}
	return 0;
}