gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
Pku 1145--Tree Summing
#include <stdio.h>
#include <memory.h>

const int MAXN = 1001 ;

int g_Sum , g_NumArr[MAXN] ; //记录所有节点的权值
bool OK , g_visible[MAXN] ; //记录哪些是叶结点

void ReExp( int &nPos, int sum )
{
    if ( OK ) return ;   //找到则返回
    
    int num = g_NumArr[nPos]  + sum ;
    if ( !g_visible[nPos + 1] && !g_visible[nPos + 2] )
    {
        if ( g_Sum == num )
            OK = true ;
        nPos += 2 ;
        return ;
    }
    nPos++ ;
    if ( g_visible[nPos] )
    {
        ReExp( nPos, num ) ;
    }
    nPos++ ;
    if ( g_visible[nPos] )
    {
        ReExp( nPos, num ) ;
    }
    
}

void Init()
{
    OK = false;

    memset( g_visible, 0, sizeof(g_visible)) ;
    memset( g_NumArr, 0, sizeof(g_NumArr)) ;
}

int main()
{
//    freopen("in.txt", "r", stdin);

    char cmd ;
    int flag, mark, num, m ;
    bool aNum ;
    while ( scanf("%d", &g_Sum) != EOF )
    {
        Init() ;
        flag = 1;
        while ( (cmd = getchar()) != '(' ) ;
        mark = 1;
        m = num = 0;
        aNum = false ;
                //处理输入数据，注意有负数
        while ( mark != 0 )
        {
            cmd = getchar() ;
            switch(cmd)
            {
            case '(':
                mark++;
                if ( aNum )
                    g_visible[m] = true ;
                aNum = false ;
                g_NumArr[m++] = num * flag;
                num = 0;
                flag = 1 ;
                break;
            case ')':
                mark--;
                break;
            case '-':
                flag = -1;
                break;
            case ' ':
            case '\0':
            case '\n':
                break;
            default:
                num = num * 10 + (cmd - '0');
                aNum = true ;
            }
        }
        
        int pos = 0 ;
        ReExp( pos, 0 ) ;

        if ( OK ){
            printf("yes\n");
        }
        else {
            printf("no\n");
        }
        

    }
    return 0 ;
}
posted on 2008-10-31 00:07 巫 阅读(299) 评论(0)  编辑 收藏 引用 所属分类: 与Tree相关的题

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理