首页 > 代码库 > UVa 112 树求和

UVa 112 树求和

题意:给定一个数字,以及一个描写叙述树的字符序列,问存不存在一条从根到某叶子结点的路径使得其和等于那个数。

难点在于怎样处理字符序列。由于字符间可能有空格、换行等。

思路:本来想着用scanf的(后发现scanf貌似不能做)。感觉太麻烦。想看网上有没有处理比較好的,一搜全是用C++的cin流的~  还是自己用C写了一下。

用的getchar()。getchar()主要就是比較繁琐。须要一个一个字符比較,记得刚開始做字符串题目时比較喜欢用getchar(),有的用scanf即可的自己也喜欢用getchar();好久没用了,写之前认为有些麻烦。

。纠结了一下~ 还是不要嫌麻烦啊。

这里还是避免了动态内存分配及释放这个易出错的东西,用一个先申请了的大Node数组anode,以及cnt记录已使用的anode的最大下标。

相同,当中用栈来匹配时,入栈和出栈的都是对应结点在anode数组中的下标值。(已经用这种方法连续做几道题了,走火入魔了~)

处理树的录入的情况是,每读一个字符分三种情况:左括号、数字、右括号,及其它忽略。

读入左括号时,若之前是在读数字(dsz为1)。则数字结束。转为int型。初始化一个Node结点。在结点入栈前,若栈非空。则该结点是栈顶元素的左或右孩子(通过结构体的lv域推断左孩子是否已赋值)。

读入数字时,非常easy,主要注意负数的情况。读入右括号时,假设上一次是读的左括号(zkh为1),则说明读的是一个空括号,这种情况下假设栈为空。则是读入了一个空树的特殊情形,若栈非空,则将栈顶元素的左或右孩子置为空,相同通过lv域来推断左右;假设读到的不是空括号,则相应栈顶元素的左右孩子均已赋值。出栈。

这样就可以建树。

只是能够发现和值在建树过程中就可以计算,仅仅要维护一个值。它是栈中元素的值之和就可以。(程序中的he值)每到叶子结点时,通过与给定的值推断。另外还需注意的就是如何跳出读取树描写叙述符字节序列的这个while循环。

这里用栈为空的时候。只是有几个特殊情况又须要fg变量进行标记,比方第一个为空格字符top本来就为0但不应跳出,比方读到空树时尽管没有数字入栈过但应该要跳出了所以置fg为1。

注意:值可为负数。(这个网搜的时候看别人提到,不知道自己会不会注意到)

本地调了几次,一次就AC了还是不错的。没有什么大错误,注意到一个数字读完后把计数置0即可了。UVa 365名还能够

Code:

#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
#define MAXN 1000

typedef struct node
{
 int data;
 int left,right;
 bool lv;//左孩子是否已赋值      
 bool lnull;//左孩子是否为空 
}Node;

Node anode[MAXN];
int cnt=0;//已经用的Node的最大下标。

位置0不用,代表空节点。

int main() { int sum=0; while(scanf("%d",&sum)==1) {//读一行 char c; bool zkh=0; char num[15]; int x=0; bool dsz=0; int stack[MAXN]; int top=0;//top始终指向栈顶元素,位置0不用,代表空栈 int he=0;//树的和值,当前栈内元素的和值。 bool flag=0; cnt=0; bool fg=0; while((c=getchar())) {//读树形式 if(c=='(') { if(dsz) { num[x]='\0'; x=0; //注意这里一个数字输入结束后需置零下标位 int nmb=atoi(num); //构造新结点 anode[++cnt].data=http://www.mamicode.com/nmb;>

这里flag=1后还是不要break比較好,由于匹配栈到空时才退出循环,不然不好推断后面的输入字符到什么时候结束,不能用换行推断。 } else//读到空括号()且栈为空,则是空树。

并把fg置1可跳出循环 { flag=0; fg=1;} } else {//出栈 he=he-anode[stack[top]].data; top--; } dsz=0; zkh=0; } if(fg&&(top==0)) break; }//while printf("%s\n",flag?"yes":"no"); } return 0; }



UVa 112 树求和