`
Jianquan
  • 浏览: 19733 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

Uva 112 Tree Summing 二叉树

    博客分类:
  • UVa
阅读更多
题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=48
主要思路:这道题目的难点在于如何把题目所给的输入数据转换成一棵树。首先定义一个字符型的变量c,再定义一个整型的变量num。因为开始一定是'(',所以先输入c(cin>>c;),然后判断,如果是'(',那么再输入num(cin>>num;),这里加一个判断,如果说cin>>num输入正常,那么输入的是一个数;如果说输入异常,那么输入的是')'。这样就可以把括号的输入和数字的输入分开了。然后就是入栈、出栈,转换成二叉树,然后再dfs。
具体代码:
#include<iostream>
#include<cstdlib>
#include<stack>
using namespace std;

struct Node
{
	int value;
	Node *left,*right;
};

int I;
bool dfs(Node *n,int sum)
{
	sum+=n->value;
	if(!n->left&&!n->right&&sum==I) return 1;
	if(n->left&&dfs(n->left,sum)) return 1;
	if(n->right&&dfs(n->right,sum)) return 1;
	return 0;
}		
int main()
{
	//freopen("in.txt","r",stdin);
	int num;
	char c;
	stack<Node *> s_Node;
	while(cin>>I)
	{
		while(!s_Node.empty()) s_Node.pop();
		int left_num=0,right_num=0;//左右括号的数目
		do
		{
			cin>>c;
			if(c=='(')
			{
				if(!(cin>>num))//如果输入异常,说明是')'
				{
					cin.clear();
					cin>>c;
					Node *tmp=NULL;
					s_Node.push(tmp);
				}
				else
				{
					left_num++;
					Node *tmp=(Node *)malloc(sizeof(Node));
					tmp->value=num;
					tmp->left=tmp->right=NULL;
					s_Node.push(tmp);
				}
			}
			else
			{
				right_num++;
				Node *tmp,*left,*right;
				right=s_Node.top();
				s_Node.pop();
				left=s_Node.top();
				s_Node.pop();
				tmp=s_Node.top();
				tmp->left=left;
				tmp->right=right;
			}
		}while(left_num>right_num);
		Node *root=s_Node.top();
		s_Node.pop();
		if(root)
		{
			if(dfs(root,0))
				cout<<"yes"<<endl;
			else
				cout<<"no"<<endl;
		}
		else
			cout<<"no"<<endl;
	}
	return 0;
}
分享到:
评论

相关推荐

    c代码-summing2.c (while)

    在给定的“c代码-summing2.c (while)”中,我们可以看到这是一个关于C语言编程的示例,其中可能涉及到了使用`while`循环来计算一系列数字的总和。`while`循环是C语言中的一种控制流程结构,用于在满足特定条件时重复...

    accumulo-column-summing-源码.rar

    这个压缩包“accumulo-column-summing-源码.rar”显然包含了Accumulo中关于列求和功能的源代码。Accumulo的核心特性之一是它的行和列的细粒度安全控制以及对数据的排序,这使得它在大数据分析领域具有很高的性能和...

    4-20mA TO 0-20mA CONVERTER AND CURRENT SUMMING CURRENT-TO-CURREN

    ### 4-20mA至0-20mA转换器及电流叠加电流转换技术 在过程控制行业中,电流环路已成为信号传输的标准方法。电流环路具有抗噪性好、不受线路阻抗误差影响的特点。Burr-Brown提供了一系列完整的单片4mA至20mA电流环路...

    2020_2021学年高中英语Unit2PoemsSectionⅡ_LearningaboutLanguageUsingLang

    【知识点解析】 这篇内容主要涉及的是高中英语的学习材料,特别是诗歌单元的学习,涵盖了语言运用、总结及学习技巧。以下是对这些知识点的详细解释: 一、词汇应用 1. "ran away" - 表示“逃跑”,在句中描述男孩...

    我收集的C程序3 我收集的C程序3

    3. **TREE.C**:这可能是一个关于树数据结构的实现,如二叉树、AVL树或红黑树。C语言可以用来构建和操作这些数据结构,实现查找、插入和删除操作。 4. **TEST.C**:通常用于测试其他函数或模块的代码,可能包含了...

    accumulo-column-summing:迭代器对跨行的列求和

    累加列求和 Accumulo 迭代器将在一组列族上执行服务器端求和。 这是对 SummingCombiner 的改进,以代码复杂性为代价,因为它减少了发送回客户端的数据量,还减少了最终客户端求和的大小。 虽然这在单机设置中通常...

    Modern Compiler Design.2nd.2012

    From the reviews of the second edition: ... Summing Up: Recommended. Computer science collections, upper-division undergraduates and above.” (C. Vickery, Choice, Vol. 50 (6), February, 2013)

    2020_2021学年高中英语Unit5FirstaidSectionⅡLearningaboutLanguageUsingLa

    ### 2020_2021学年高中英语Unit5 First aid SectionⅡ Learning about Language Using Language Summing Up & Learning Tip #### 一、关键知识点解析 **标题与描述解析:** - **标题:“2020_2021学年高中英语...

    控制工程基础:2.5 控制系统的方块图及其化简.ppt

    方块图元素包括方块(Block Diagram)、比较点(Summing Point)、分支点(Branch Point)等。基本概念及术语包括前向通路传递函数 G(s)、反馈回路传递函数 H(s) 和开环传递函数等。 1. 方块图元素 (1)方块...

    DGCNN-master.zip

    DGCNN features a propagation-based graph convolution layer to extract vertex features, as well as a novel SortPooling layer which sorts vertex representations instead of summing them up.

    Python Cookbook, 2nd Edition

    Summing Durations of Songs Recipe 3.5. Calculating the Number of Weekdays Between Two Dates Recipe 3.6. Looking up Holidays Automatically Recipe 3.7. Fuzzy Parsing of Dates Recipe 3.8. ...

    PanoplyWin-4.12.11.zip

    Combine two geo-referenced arrays in one plot by differencing, summing or averaging. Plot lon-lat data on a global or regional map using any of over 100 map projections or make a zonal average line ...

    选修六Unit1 Art Period 6.doc

    这一课时包含了以下几个部分:总结(Summing Up)、学习技巧(Learning Tip)、自我检测(Checking Yourself)以及其他巩固练习。通过这些环节,学生不仅能够回顾本单元的核心主题、词汇和语法,还能够在老师的引导...

    运放电路集锦

    反相求和放大器(Inverting Summing Amplifier) 这种电路允许多个输入信号在反相端叠加,并通过单一运放进行放大和求和。输出电压为各输入电压与各自电阻比的乘积之和的负值。 ### 5. 非反相求和放大器(Non-...

    Graph Theory 3E Adrian Bondy, U.S.R Murty

    Graphs - Subgraphs - Connected Graphs - Trees - Separable and Nonseparable Graphs - Tree-Search Algorithms - Flows in Networks - Complexity of Algorithms - Connectivity - Planar Graphs - The Four-...

    MC1458 友顺UTC 电子元器件芯片.pdf

    该芯片具有低功耗、宽输入电压范围、无 latch-up、高速增益和短路保护等特点,适用于 summing 放大器、电压跟随器、积分器、活动滤波器、函数生成器和一般反馈应用。 特点 * 低功耗 * 宽输入电压范围 * 无 latch-...

Global site tag (gtag.js) - Google Analytics