点击打开链接http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=48
题目意思:给定一个字符串,把字符串里面的数字建成一颗树,数字有可能是负号,所以这一题其实有很多可以学的,比如怎样输入会有多行,还有怎么建立一颗树,等等。
解题思路:我们用一个字符数组来存储读入的字符串,用一个栈来存储括号,判断如果栈为空并且读到换行那么就退出。我们可以先把根节点建好,建根节点调用creatnode()函数,注意数字可能是1234 -1234这些情况,所以判断.然后我们在从根节点后面的位置开始变量字符数组,如果是(‘(’)则判断下一额是数字还是右括号,如果是数字则continue,如果是右括号则,执行creatnode()函数产生新的节点。中间数字有可能是多位的情况,所以要做好处理,即传入creatnode()的参数要做好。树建好以后就是搜素路径和是否为sum,我们用深搜来处理,(中间可以用前序遍历来判断是否建好了树),我们知道对于叶子节点,那么它的两个子树的al都是Min,所以在搜索时候处理做好即可。
代码:
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <stack>
#include <list>
#include <algorithm>
using namespace std;
const int Min = -999999999;//定义一个宏为无穷小,后面遇到左括号后面没有数字时要处理
char ch , c[50000];//字符数组存储字符串
int sum, tempsum, mark, cmark, Found , len;
stack<char>st;//栈存储括号
//二叉树的结构体
struct node {
int val;
struct node *lchild, *rchild, *father;//用一个father指针来指向当前指针cur的父亲节点
};
node *root, *temp, *cur;
//初始化函数用来对每一个node 指针初始化
void init(node *u , int m) {
u -> father = NULL;
u -> lchild = NULL;
u -> rchild = NULL;
u -> val = m;
}
//建立新的节点
void createnode(int n) {
temp = new node;
init(temp , n);//初始化temp,临时的指针
if (cur->lchild == NULL) {//如果左子树为空,把temp赋给左子树
cur -> lchild = temp;
temp = cur;//temp存储此时的cur
cur = temp -> lchild;//当前指针指向左子树
}
else {//如果右子树为空,把temp赋给右子树
cur -> rchild = temp;
temp = cur;
cur = temp -> rchild;
}
cur -> father = temp;//cur的父亲节点为temp
}
//创建根节点函数(最开始用到)
int creatroot() {
int i = 1 , j , k ,tempnum = 0, cmark = 1;
if (c[1] == '-') { //如果有负号要处理
cmark = -1 , i = 2 ;
}
j = i;
while(isdigit(c[j]))
j++;
j--;
for(k = 0 ; j >= i ; j-- , k++)
tempnum += (pow(10 , k)) * (c[j] - '0');
init(root , cmark * tempnum);//建立根节点
cur = root;//当前节点赋给根节点
i += k;
return i;
}
//输入函数
void input(){
int i = 0;
while(ch = getchar()){
if(ch == ' ' || ch == '\n')//判断跳过函数
continue;
else{
c[i] = ch;
if(c[i] == '(') st.push(c[i]);
if(c[i] == ')') st.pop();
if(st.empty()) return;//栈为空则退出
i++; len = i;
}
}
}
//处理函数
void solve(int i) {
int mark = 1;//mark用来标记是正数还是负数
while (i <= len){
if (c[i] == '-') {//遇到符号则把mark标记为-1
mark = -1;
i++;
continue;
}
if (c[i] == ')') {//遇到右括号则cur指向它的父亲节点
cur = cur -> father;
i++;
mark = 1;
continue;
}
if (isdigit(c[i])) {//如果是数字进行产生
int tempnum = 0 , j , k;
j = i + 1;
while(isdigit(c[j])){
j++;
}
j--;
for(k = 0 ; j >= i ; j-- , k++){
tempnum += (pow(10 , k)) * (c[j] - '0');//里面有多个数字情况
}
createnode(mark * tempnum);
i += k;
mark = 1;
continue;
}
if (c[i] == '(') {
if(c[i+1] == ')')
createnode(-999999999);
i++;
mark = 1;
continue;
}
}
}
//dfs搜索函数路径值函数
void judge(int tempsum, node *cur) {
temsum += cur->val;
if (Found)
return;
if (tempsum == sum && cur->lchild->val == Min && cur->rchild->val == Min) {//说明找到了该路径
Found = 1;
}
if (cur -> lchild != NULL && cur -> lchild -> val != Min)
judge(tempsum , cur -> lchild);//继续向左儿子搜素
if (cur -> rchild != NULL && cur -> rchild -> val != Min)
judge(tempsum , cur -> rchild);//继续像右儿子搜素
}
//栈清空
void clear() {
while (!st.empty())
st.pop();
}
//主函数
int main(){
int i;
while (~scanf("%d", &sum)) {
root = new node;
Found = 0;
input();
if(len == 1) { //如果是这种 5 () 这种情况直接输出
printf("no\n") ; continue;
}
if(len != 1) {
i = creatroot() , solve(i);//调用函数
}
judge(0 , root);//搜索
if (Found) printf("yes\n");
if (Found == 0) printf("no\n");
clear();//栈清空
}
return 0;
}
分享到:
相关推荐
accumulo-column-summing-源码.rar
c代码-summing2.c (while)
4-20mA TO 0-20mA CONVERTER AND CURRENT SUMMING CURRENT-TO-CURREN
2020_2021学年高中英语Unit2PoemsSectionⅡ_LearningaboutLanguageUsingLanguageSummingUp&LearningTip习题含解析新人教版选修6
累加列求和 Accumulo 迭代器将在一组列族上执行服务器端求和。 这是对 SummingCombiner 的改进,以代码复杂性为代价,因为它减少了发送回客户端的数据量,还减少了最终客户端求和的大小。 虽然这在单机设置中通常...
Neutron stimulated emission computed tomography (NSECT) is a new approach for biological spectroscopy and imaging. Since the<BR>gamma-ray photons emitted from stimulated element have energies from 100...
Summing Bird—用Scalding 和 Storm进行Streaming MapReduce
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)
Summing Up 33 Other Linkages 33 Manager’s Checklist for Chapter 237 3. Understanding Performance—Good and Bad 38 What Do We Mean by “Performance”? 39 The Stuff of Performance—Good and Poor 42 ...
From the reviews: ... presented in the text … Summing Up: Highly recommended Upper division undergraduate through professional collections " J Y Cheung Choice Vol 47 2 October 2009 ...
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.
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. ...
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 ...
Graphs - Subgraphs - Connected Graphs - Trees - Separable and Nonseparable Graphs - Tree-Search Algorithms - Flows in Networks - Complexity of Algorithms - Connectivity - Planar Graphs - The Four-...
对设计/前面板进行了一些调整,决定在夏季添加Summing Junction输入是一个好主意。 开始一个。 2020-12-08哇,距离我上次在这里更新内容已经很长时间了。 适度的理由:大约一年前,我意识到我同时在进行多个项目...
Summing Up Continuous Delivery .................................................................................. 22 Puppet Enterprise: Automate and Make Your Life Better. ...............................
Multi-kernel classifiers, however, are capable of integrating spectral features with spatial or structural features using multiple kernels and summing them for final outputs. Using a support vector ...
Considering the extremely wide bandwidth, we use 20-μm-thick BBO crystal as the nonlinear medium, and correct the spectral response with the frequency summing efficiency. Spatial splitting is ...