2014-01-09

UVa 112 Tree Summing ——字符串处理（大误）

今天写了一道十分有感觉的字符串处理题目。

题目简介

原题：UVa 112 Tree Summing

题目给出了一个十分具有Lisp风格的字符串，来表示一个二叉树，就像这样：

(5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))

所要完成的任务是：判断每条从根部到叶子的路径上数的和是否等于一个给定的常数，如果是，则输出“yes”，否则输出“no”。

虽然是二叉树的题目，但是并不需要建立二叉树。只需调用递归函数，由系统来创建基于函数的二叉树。

所以我才说这题是字符串处理嘛~~~~

题目分析

这题有几个坑的点。

空树，就像这样

0 () 

这种东西按照题目要求是要输出”no”的。在有些代码里面不需要特殊判断。

负数

5 (18 ( - 13 ( ) ( ))()) 

如果像我一样自己处理读入的数，就一定要注意负数的问题。这题负数就坑到我一回。在以上的测试样例中应该返回”yes”

叶子结点指的是左子树和右子树都为空的结点。

在我的第一个版本的代码里面，就是在左子树或右子树有一个为空时就输出了当前的和。

20 (5 () (5 () (5 () (5 () (4 () () ) ) ) ) ) 

刚好就撞到了上面这组测试数据的枪口上。。。

我的实现

不得不说我还是对C语言十分的喜爱啊。。

虽然打开编译器创建了一个test26.cpp的文档，想写个C++来做这件事情。但是写完之后才发现，我还是只用了#include <stdio.h> 一个头文件。

1. 宏Getchar(x)

计算机读取数据是个十分矛盾的过程，比如我想要读取一个数字，读到左括号那里结束。但是如果我不读取出那个左括号，我就不知道我数字已经读取结束了。如果读出了那个左括号，我又相当于多读了一个东西。

所以我用了一个变量buffer存储这个多读出来的值，用另一个变量bufflag标志有没有使用这个buffer。

在此基础上我重写了getchar，如果buffer正在使用，则返回buffer中的值，否则返回输入流的下一个字符。

代码如下：

if(bufflag) { 
    bufflag = 0; 
    x = buffer; 
} else {
    x = getchar(); 
}

2. 宏jumpSpace(x)

题目要求是这个字符串中间可以有任意的空白字符。于是我写了这个宏用来跳过中间所有的空白字符。

这个宏会循环调用宏Getchar(x)，直到它找到一个不是空白字符的字符，并把结果返回给x。

代码如下：

do { 
    Getchar(x); 
} while (x == ' ' x == '\n' x == '\t' ); 

3. 宏ispnum(ch)

这个宏只被调用了一次。它用来判断读到的内容是不是一个数字。

注意，由于存在负数，所以如果读到-，也将被视为读到了一个数字，它代表即将读到的数是个负数。

实际上此时ch可能的值只有数字、-和)。其他的值都是不正确的。

代码如下：

ch=='-'?1:(ch>='0'&&ch<='9'?1:0) 

4. 宏nextNum(ch)

这个宏用来整理接下来即将从输出流中读出的一个整数。

如果ch为一个数字，接下来就会调用这个宏来找出以这个数字开头的完整的整数。这个宏将一直读到遇到第一个不是数字的地方停止。

但是此时它已经从输入流里读出了多余的东西。所以在这个宏的末尾，需要把这个多读出来的东西写入buffer。

代码如下：

if(ch == '-') { 
    scanf("%d", &ch); 
    ch = -ch; 
} else { 
    ch -= '0'; 
    Getchar(k); 
    while(k >= '0' && k <= '9') { 
        ch = ch * 10 + ( k - '0' ); 
        Getchar(k); 
    } 
    buffer = k; 
    bufflag = 1; 
} 

完整AC代码如下：

#include <stdio.h> 
#define Getchar(x) if(bufflag){bufflag=0;x=buffer;}else x=getchar() 
#define jumpSpace(x) do{Getchar(x);}while(x==' 'x=='\n'x=='\t') 
#define ispnum(ch) ch=='-'?1:(ch>='0'&&ch<='9'?1:0) 
#define nextNum(ch) if(ch=='-'){scanf("%d",&ch);ch=-ch;}else{ch-='0';\ 
                Getchar(k);while(k>='0'&&k<='9'){ch=ch*10+(k-'0');Getchar(k);}\ 
                buffer=k;bufflag=1;} 
int caseNum; 
int flag; 
int buffer; 
int bufflag=0; 
int Insert(int sum){ 
    int ch; 
    int num; 
    int k; 
    jumpSpace(ch); 
    jumpSpace(ch); 
    if(ispnum(ch)){ 
        nextNum(ch); 
        num=sum+ch; 
        if(Insert(num)&Insert(num)) 
        if(num==caseNum) 
        flag=1; 
    }else return 1; 
    jumpSpace(ch); 
    return 0; 
} 
int main(int agrc, char *agrv[]) { 
    while(scanf("%d",&caseNum)!=EOF) { 
        flag=0; 
        Insert(0); 
        flag?printf("yes\n"):printf("no\n"); 
    } 
    return 0; 
} 

main