uva_112-Tree Summing

来源:岁月联盟 编辑:猪蛋儿 时间:2012-11-15
[cpp] 
/**这道题的难度在于建树,因为输入可能不在一行,所以不能用字符串接收
 *必须一个一个读,我这里是用getchar(),(当然scanf也行),每次读取到
 *‘(’时,开始接收数据,如果是‘)’,子树为空,否则的话就是数字(可能是
 *负数),这里有一个注意的地方就是空格,也坑了我很久,当时没有想到windows
 *和linux的差异,最后用库函数isspace解决。。。
 */ 
#include <cstdio> 
#include <cctype> 
using namespace std; 
 
struct Node { 
    int v; 
    Node *lc, *rc; 
}; 
 
bool flag; 
 
void pre_create_tree(Node *&root) { 
    char c; 
    int v = 0, leap = 0; 
    if( !flag ) while( getchar() != '(' ); 
    while( c = getchar() ){ 
        if( isspace(c) ) continue; 
        if( c == '(' || c == ')' ) break; 
        if( c == '-' ) {leap = 1; continue ;} 
        v *= 10; 
        v += c - '0'; 
    } 
    if( ')' == c ){ 
        root = NULL; 
        flag = false; 
    } 
    else { 
        flag = true; 
        if( leap ) v = -v; 
        root = new Node; 
        root->v = v; 
        pre_create_tree(root->lc); 
        pre_create_tree(root->rc); 
    } 

 
void pre_traverse(Node *root, int ans){ 
    if( flag ) return ; 
    if( !root ) return ; 
    ans -= root->v; 
    if( root->lc ) pre_traverse(root->lc, ans); 
    if( root->rc ) pre_traverse(root->rc, ans); 
    if( !ans && !root->lc && !root->rc ) flag = true; 

 
int main(int argc, char const *argv[]) { 
#ifndef ONLINE_JUDGE 
    freopen("test.in", "r", stdin); 
#endif 
    int ans, c; 
    while( ~scanf("%d", &ans) ) { 
        Node *root; 
        flag = false; 
        pre_create_tree(root); 
        while( c = getchar() ){ 
            if( c == '/n' ) break; 
            if( c == EOF ) break; 
        } 
        pre_traverse(root, ans); 
        if( flag ) printf("yes/n"); 
        else printf("no/n"); 
 
    } 
    return 0;