[表达式]真假计算
题目描述
有一棵树,不一定是二叉树。
所有叶子节点都是 True
或者 False
。
对于从上往下奇数层的非叶子节点是 and
,偶数层非叶子节点为 or
。
树上每个节点的值是所有孩子节点的值进行该节点的运算操作。
判断一棵树能否砍掉,最快的方法就是从叶子节点一路“与” 和 “或” 到根节点,得到整颗树的真假值后进行决断。
树以简单的括号序列给出:上图可以描述为
(
(
A
(
B
C
)
)
(
D
E
)
)
((A(BC))(DE))
((A(BC))(DE))。
输入格式
数据包括若干组,每组数据包含一行一个字符串,输入 ( ) () () 表示结束。
输出格式
每组数据输出一行,包含:数据编号,点,空格,true
或 false
。
样例
样例输入1:
((F(TF))(TF))
(TFT)
((TFT)T)
()
样例输出1
1. false
2. false
3. true
数据范围
对于
10
%
10\%
10% 的数据:每行只包含一对括号;
对于
30
%
30\%
30% 的数据:只有嵌套的括号,没有并列的括号;
对于
100
%
100\%
100% 的数据:测试数据少于
1000
1000
1000 组,字符串长度小于
32000
32000
32000。
题解
直接进行递归,记录层数。
- 如果当前字符为
(
,说明要进入下一层,进行下一层递归。 - 如果当前字符为
)
,说明当前层结束,返回答案。 - 如果当前字符为
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;
}