#UVa:112-Tree Summing

灆洢 2015-05-22 16:25:09

可以利用編譯器最基本的技術去寫這題,一個負責剖析出各個token,一個去確定Grammer是不是對的。藉由剖析的過程中,順便去加總值看是否與目標值相同即可得解。

Token

  • ( : LEFT_BRACKET
  • ) : RIGHT_BRACKET
  • -?[0-9]+ : NUMBER

Grammer

  • Tree: <Node> | <NullNode>
  • Node: LEFT_BRACKET NUMBER <Tree> <Tree> RIGHT_BRACKET
  • NullNode: LEFT_BRACKET RIGHT_BRACKET

C++(0.043)

/*******************************************************/
/* UVa 112 Tree Summing                                */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2015/05/22                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;

enum Token {
  LEFT_BRACKET, RIGHT_BRACKET,
  NUMBER
};

enum Tree {
  NULLNODE, NODE 
};

Token getToken(int &token){
  int c = getchar();
  while( c == ' ' || c == '\n' ){
    c = getchar();
  }

  if( c == '(' ) return LEFT_BRACKET;
  if( c == ')' ) return RIGHT_BRACKET;

  int sign = 1;
  if( c == '-' ){
    sign = -1;
    c = getchar();
  }

  token = 0;
  while( isdigit(c) ){
    token = token * 10 + (c - '0');
    c = getchar();
  }

  token *= sign;
  ungetc(c, stdin);

  return NUMBER;
}

Tree parseTree(bool &isMatched, int rootSum, int target){
  int token;
  getToken(token); // '('

  if( getToken(token) == RIGHT_BRACKET ){
    return NULLNODE;
  }

  rootSum += token;

  Tree leftSubTree = parseTree( isMatched, rootSum, target );
  Tree rightSubTree = parseTree( isMatched, rootSum, target );

  getToken(token);

  if( leftSubTree == NULLNODE && rightSubTree == NULLNODE ){
    if( rootSum == target ){
      isMatched = true;
    }
  }

  return NODE;

}

int main(){
  int target;
  while( scanf("%d", &target) != EOF ){
    bool isMatched = false;
    parseTree(isMatched, 0, target);
    if( isMatched ){
      printf("yes\n");
    }  
    else {
      printf("no\n");
    }
  }
  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料