ACM: 112 - Tree Summing

這題要讀取以字串表現的binary tree，並找出是否有root-to-leaf path能產生指定的數字和。因為字串跟數字混在一起，如何處理字串可說是這題的罩門，但其實想清楚了這題S-expression的模式，字串處理起來就沒有想像中的複雜了。

因為原本卡在如何擷取字串，也是第一次寫bin tree的東西，所以寫出來很開心！再進了百大，超超興奮！

TIPS

1. 數字會有負數
2. 注意 0 () 的測資，output應該要是 no

CODE

#include <stdio.h>

int a, found;

int tree(int parent_sum);
int makenum(int *a, int n, int sign);

int main(){
  char c;
  
  while( scanf("%d", &a) != EOF ){
    while( (c = getchar()) !=EOF )
      if( c == '(' )
        break;
    
    found = 0;
    tree(0);
    if( found == 1 )
      printf("yes\n");
    else
      printf("no\n");
  }/*while*/
  
  exit(0);
}

/*return 0 if is empty node*/
int tree(int p){
  int sign, line[10], e, num;
  int flag, le, re;
  char c;
  
  flag = le = re = 1;
  sign = 1;
  e = num = 0;
  while( flag == 1 ){
    c = getchar();
    
    if( c == '-' )
      sign = -1;
    else if( c >= '0' && c <= '9' ){
      line[e] = c - '0';
      e++;
    }
    else if( c == '(' ){
      /*make number*/
      num = makenum(line, e, sign);
      
      /*left tree*/
      if ( tree( num+p ) == 0 )
        le = 0;

      /*read '('*/
      while( (c = getchar()) !=EOF )
        if( c == '(' )
          break;

      /*right tree*/
      if ( tree( num+p ) == 0 )
        re = 0;
    }
    else if( c == ')' )
      flag = 0;
    else ;
  }/*while flag is 1*/
  
  if( (le + re == 0) && ((num+p) == a) ){
    found = 1;
    return 1;
  }
  
  if( e == 0 )
    return 0;
    
  return 1;
}

int makenum(int *a, int n, int sign){
  int i, j, p, r;
  
  r = a[n-1];
  p = 1;
  for(i=0; i<(n-1); i++){
    for(j=1; j<=(n-i-1); j++)
      p *= 10;
    r += ( a[i] * p );
  }
  r *= sign;
  
  return r;
}