青岛建设系统一体化网站软文营销案例200字

题目描述

有一棵树，不一定是二叉树。
所有叶子节点都是 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;
}