长兴县住房建设局网站,wordpress个人主页插件,成都网站设计服务商,如何建手机销售网站题目描述
有一棵树#xff0c;不一定是二叉树。 所有叶子节点都是 True 或者 False。 对于从上往下奇数层的非叶子节点是 and#xff0c;偶数层非叶子节点为 or。 树上每个节点的值是所有孩子节点的值进行该节点的运算操作。 判断一棵树能否砍掉#xff0c;最快的方法就是从…题目描述
有一棵树不一定是二叉树。 所有叶子节点都是 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;
}
